Bard College

Bard Digital Commons

Senior Projects Spring 2013 Bard Undergraduate Senior Projects

2013

Implementation of the Solution to the Conjugacy

Problem in ompson's Groups

Nabil Tarique Hossain

Bard College

is Access restricted to On-Campus only is brought to you for free and

open access by the Bard Undergraduate Senior Projects at Bard Digital

Commons. It has been accepted for inclusion in Senior Projects Spring

2013 by an authorized administrator of Bard Digital Commons. For more

information, please contact digitalcommons@bard.edu.

Recommended Citation

Hossain, Nabil Tarique, "Implementation of the Solution to the Conjugacy Problem in ompson's Groups" (2013). Senior Projects

Spring 2013. Paper 45.

hp://digitalcommons.bard.edu/senproj_s2013/45

Implementation of the Solution to the

Conjugacy Problem in Thompson’s

Groups

A Senior Project submitted to

The Division of Science, Mathematics, and Computing

Bard College

Nabil Hossain

Annandale-on-Hudson, New York

May, 2013

Abstract

In this project, we present an eﬃcient implementation of the solution to the conjugacy

problem in Thompson’s group F , a certain inﬁnite group whose elements are piecewise-

linear homeomorphisms of the unit interval [0, 1]. Our algorithm checks for conjugacy by

constructing and comparing directed graphs called strand diagrams. We provide a compre-

hensive description of our solution algorithm, including the data structure we used to hold

strand diagrams and the additional subroutines for manipulations of strand diagrams. We

prove that our algorithm theoretically achieves an O(n) bound in the size of the input,

and we present a O(n

) working solution as an executable JAR ﬁle, a web application,

and Java source code.

Contents

Abstract 1

Dedication 6

Acknowledgments 7

Introduction 9

1 Background 12

1.1 Conjugacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2 Directed Graphs Embedded on Surfaces . . . . . . . . . . . . . . . . . . . . 15

1.3 Thompson’s Group F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.3.1 Dyadic Rearrangements . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.3.2 Tree Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.4 Strand Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.4.1 Strand Diagram Manipulations . . . . . . . . . . . . . . . . . . . . . 28

2 Annular Strand Diagrams 31

2.1 Closing Strand Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.2 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.3 Concentric Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.4 The Cutting Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.5 Isotopy of Reduced Annular Strand Diagrams . . . . . . . . . . . . . . . . . 43

3 Algorithm for the Conjugacy Problem in F 47

3.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.2 The Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.2.1 Background: Doubly Linked Lists . . . . . . . . . . . . . . . . . . . . 50

Contents 3

3.2.2 Class: Edge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.2.3 Class: Vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.2.4 Class: Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.2.5 Class: Strand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.2.6 Class: Annular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.3 Strand Diagram Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.4 Reducing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.4.1 Keeping Track of Potential Future Reductions . . . . . . . . . . . . . 60

3.4.2 Cutting Path Update and Free Loop Generation . . . . . . . . . . . 61

3.5 Connected Component Labeling . . . . . . . . . . . . . . . . . . . . . . . . 66

3.6 Encoding Annular Strand Diagrams into Planar Graphs . . . . . . . . . . . 67

3.6.1 The Encoding Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 72

3.7 Retrieving Annular Strand Diagrams from Planar Graph Encodings . . . . 72

3.8 Isomorphism Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

3.9 Our Actual Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

3.9.1 Isotopy Detector Given two Corresponding Vertices . . . . . . . . . 76

3.9.2 Isotopy Detector Given two Connected Reduced Annular Strand

Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

3.10 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

3.10.1 Veriﬁcation of Results . . . . . . . . . . . . . . . . . . . . . . . . . . 80

3.10.2 Shortest Cyclically Reduced Word for the Identity . . . . . . . . . . 82

3.11 The Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

3.11.1 The Variants and the Implementation Details . . . . . . . . . . . . . 83

3.11.2 Using the Application . . . . . . . . . . . . . . . . . . . . . . . . . . 84

4 Conclusion and Future Work 90

Appendix: Algorithm Descriptions 92

Bibliography 99

List of Figures

1.2.1 Homotopy of curves on the plane. . . . . . . . . . . . . . . . . . . . . . . . . 18

1.2.2 Isotopy of graphs on the plane. . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.2.3 A, B, and C are diﬀerent embeddings of the same planar graph. None of

the embeddings are isotopic on the plane, but B and C are isotopic on the

sphere. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.3.1 Generators for Thompson’s Group F . The right half of x

is the same as x

. 24

1.3.2 The inﬁnite binary tree of standard dyadic intervals in [0, 1] (image taken

from [2]). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.4.1 A strand diagram, a merge, and a split (image taken from [3]). . . . . . . . 26

1.4.2 Construction of the strand diagram for x

from its tree diagram (image

taken from [3]). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1.4.3 Generators for F and their inverses. . . . . . . . . . . . . . . . . . . . . . . 28

1.4.4 The two reduction rules (image taken from [3]). . . . . . . . . . . . . . . . . 28

1.4.5 Composing elements of F by concatenating their strand diagrams. Note

that the concatenation makes a type II reduction move possible around the

vertex v

(image taken from [3]). . . . . . . . . . . . . . . . . . . . . . . . . 29

2.1.1 Annular strand diagram for x

obtained by closing its strand diagram . . . 32

2.2.1 The reduction moves for annular strand diagrams. A type I move is allowed

when the shaded region is a topological disk. A type III move is allowed

when the space between the two free loops is a topological annulus contain-

ing no vertices (image taken from [3]). . . . . . . . . . . . . . . . . . . . . . 32

2.2.2 A type I move reduces the central annular strand diagram to a free loop,

but a reduction II creates two concentric free loops. A reduction III on the

diagram in the right merges the two free loops, preserving unique normal

forms (image taken from [3]). . . . . . . . . . . . . . . . . . . . . . . . . . . 33

LIST OF FIGURES 5

2.2.3 Reducing an annular strand diagram. In the pictures, the green regions are

subject to type I moves, and the red and blue regions are each subject

to type II moves. The type II move on the red region in (a) breaks the

connected annular strand diagram into two connected components. . . . . . 34

2.3.1 A reduction II move causing a connected component to split into two (each

shaded region represents a component). . . . . . . . . . . . . . . . . . . . . 36

2.3.2 Two reduced annular strand diagrams (A

has been taken from [3]). . . . . 37

2.4.1 For a cutting path, the edge crossing in (a) is allowed and (b) is not allowed 40

2.4.2 Update of the cutting path for each reduction move. . . . . . . . . . . . . . 41

2.4.3 Status of a cutting path (a) after closing a strand diagram (crosses edge e

(b) after performing a type II reduction, and (c) after the annular strand

diagram is reduced. The numbers denote the order of the edges in the

cutting path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.5.1 Three reduced annular strand diagrams in which A

and A

are isotopic. . 45

3.1.1 Overview of the solution algorithm for the conjugacy problem in F . . . . . 49

3.2.1 The Java model of the data structure used for the solution to the conjugacy

problem in F . Note that all the linked lists are doubly linked. . . . . . . . . 52

3.4.1 (a) Reduction I and (b) reduction II, with labeled edges and the split in-

volved in the reduction labeled v. The green vertices can be splits or merges,

they may not be distinct from each other or from the yellow vertices. . . . . 58

3.4.2 Special cases for updating cuttingPath during a type II move. Refer to (b)

in Figure 3.4.1 for edge and vertex labels. . . . . . . . . . . . . . . . . . . . 66

3.6.1 The encoding of s ∈ X when s is a free loop. φ(s) ∈ G is the planar graph

with a single vertex having a loop. . . . . . . . . . . . . . . . . . . . . . . . 68

3.6.2 Diﬀerent input and output types for edges. The vertex on the left is a merge,

and the one on the right is a split . . . . . . . . . . . . . . . . . . . . . . . . 69

3.6.3 (a) shows the highlighted edge e

which is the lone output of a merge and

the lone input to a split. The encoding of e

produces the planar graph g

in (b). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

3.6.4 Encoding of x

to its corresponding planar graph. . . . . . . . . . . . . . 70

3.10.1A general structure for reduced annular strand diagrams with two vertices.

The red dashed circles show free loops. . . . . . . . . . . . . . . . . . . . . . 80

3.11.1The user interface of the application for the conjugacy problem in F . . . . . 83

Dedication

To my father, mother, brother, and sister, who all make my world magical

Acknowledgments

Most of the credits for this project’s success goes to my adviser James Belk, an excellent

researcher, a wonderful teacher, and a very good friend. I will be always surprised at how

he managed to advise four long senior projects simultaneously with ease. I also thank him

for the skeleton program in Mathematica that supports basic strand diagram drawing.

Special thanks to my other adviser Robert McGrail, whose expertise in algorithms, and

feedback on this writeup have been invaluable, and whose Friday barbecues were equally

phenomenal. Plus he has been a wonderful career adviser, helping me to identify my own

interests in science.

I would like to take this opportunity to thank all my teachers who have prepared me for

future endeavors. Speciﬁcally I mention the name of Keith O’Hara whose Intro to Object

Oriented Programming course got me to switch my major from Physics to Computer

Science. Sven Anderson, I greatly beneﬁted from consulting with you about the Java

implementation issues regarding this project. And of course, Becky Thomas, whose classes

have cemented my foundations on computer science. Her Theory of Computation course

was fantastic, specially in the amount of material covered.

I thank all the friends who have supported me the last four years, making Bard feel

homely. Anis Zaman, you have been an incredible friend, and more than that, like a

brother. I will always remember the wonderful times we shared, and the way we stuck

together during times of frustrations. Azfar Khan, you are a great roommate, and the top

chef in the house without a question. Blagoy Kaloferov, I will not forget the late night

FIFA games during stressful times, and also the free car rides to my apartment. Weiying

Liu, Nazmus Saquib, and Prabarna Ganguly, you guys leave deep impressions sketched in

my mind that I will never forget.

I am grateful to my guardians in the USA - Anowar Hasan, Fauzia Parvin, Mustaﬁzur

Rahman, and Mostofa Mohammad. Whenever I sought your help or advise, you oﬀered

them without any hesitation.

By thinking about two wonderful siblings who are willing to give away everything for

me, I stay away from the wrong path and learn to be more responsible. I feel very lucky

to be their big brother, and I am equally proud of them.

Lastly, I can never repay the enormous debt I owe to my parents, who have made

unimaginable sacriﬁces towards my success. You show me hope in my distress, you teach

me to stand up and ﬁght, you have faith in me in my darkest moments, and you are the

reason I am here today.

Introduction

Thompson’s groups are certain inﬁnite groups that are considered interesting in the ﬁelds

of geometric group theory and homotopy theory. There are three such groups, called F,

T, and V, deﬁned by Richard J. Thompson in the 1960s. The elements of F are piecewise

linear homeomorphisms of the interval [0, 1] with ﬁnitely many breakpoints satisfying

certain conditions, with function composition as the group operation. T and V are similar

to F except T consists of homeomorphisms of the circle, and V the homeomorphisms of

the Cantor set. For a comprehensive introduction to these groups, the reader is referred

to Canon, Floyd and Perry [4].

In a group, the conjugacy problem is the problem of determining whether any two

elements are conjugate. It was introduced by the mathematician Max Dehn in 1911 as

one of three fundamental algorithmic problems in the study of inﬁnite groups [5]. The

conjugacy problem is not solvable in general [15], but solutions to the conjugacy problem

are known for many important classes of groups such as free groups, surface groups, braid

groups and so forth.

INTRODUCTION 10

Guba and Sapir [8, 9] provided a solution to the conjugacy problem in F using graphs

called diagrams. Building upon this solution, Belk and Matucci [3] introduced certain

directed graphs called strand diagrams, and showed the existence of a solution to the

conjugacy problem for all Thompson’s Groups using these strand diagrams.

In this project, based on the methods in [3], we make the solution to the conjugacy

problem in F precise, show that our solution executes in linear time, and present an

eﬃcient implementation of this solution as an application.

Given two input elements of F , our solution algorithm eﬃciently constructs the corre-

sponding strand diagrams, modiﬁes them using certain operations such as closing, con-

catenation, and reduction, and eventually compares the resulting strand diagrams to see

if they are the same. We also present an eﬃcient data structure to hold and manipulate

strand diagrams in such a way that is geared towards achieving the fastest possible running

time of the algorithm.

We prove that the best algorithm solving the conjugacy problem in Thompson’s Group

F is of the order O(n), where n is the sum of the length of the two input elements compared

for conjugacy. However, note that this proof uses the linear time algorithm proposed by

Hopcroft and Wong [10] to determine whether two planar graphs are isomorphic, which

has not been implemented to date because of its complicated design. As a result, our

implementation replaces the isomorphism check between two planar graphs with an alter-

native method that directly compares two strand diagrams to determine whether they are

the same. Due to this change, our implementation takes quadratic time.

We release a Java implementation of our solution algorithm as a web application, an

executable JAR ﬁle, and the source code. As far as we know, this is the ﬁrst implementation

of the solution to the conjugacy problem in F . We hope that it will be helpful to researchers

in studying Thompson’s Groups.

INTRODUCTION 11

The rest of this paper is organized as follows:

Chapter 1 provides all the relevant background information and the deﬁnitions which

will be used throughout the paper; Chapter 2 introduces and discusses the structure of

annular strand diagrams, which are obtained from strand diagrams, and used in our

solution algorithm; Chapter 3 provides a comprehensive description of the algorithm for

the conjugacy problem in F along with details on how to use our software; Chapter 4

concludes the paper, drawing attention to future work; and ﬁnally in the Appendix some

of the important sub-algorithms in our implementation are detailed.

Background

1.1 Conjugacy

Deﬁnition 1.1.1. In a group G, elements g

, g

∈ G are conjugate if there exists an

element h ∈ G such that g

= hg

−1

. In this case, we say that g

is the conjugate of g

by h, or h conjugates g

to g

. 4

Conjugacy is an equivalence relation, which partitions G into equivalence classes, known

as conjugacy classes. Every element of a group belongs to one conjugacy class only, and

two elements g

and g

are conjugate if and only if they belong to the same conjugacy

class.

Example 1.1.2. Two permutations in the symmetric group S

are conjugate if and

only if the permutations have the same cycle structure (See [6], Proposition 4.3.11). For

instance, the group S

has 3! = 6 permutations of the set P = {1, 2, 3}. In cycle notation,

= {(1), (1 2), (1 3), (2 3), (1 2 3), (1 3 2)}. There are three conjugacy classes of S

1. The identity (1) is conjugate only to itself: {(1)}

• (1) = (1)(1)(1)

−1

1. BACKGROUND 13

2. The 2-cycles: {(1 2), (2 3), (1 3)}

• (1 2) = (1 3)(2 3)(1 3)

−1

• (1 2) = (2 3)(1 3)(2 3)

−1

3. The 3-cycles: {(1 2 3), (1 3 2)}

• (1 2 3) = (1 2)(1 3 2)(1 2)

−1

For the following deﬁnition, we assume that the reader is familiar with the term gener-

ating set. Recall the deﬁnition of a word.

Deﬁnition 1.1.3. In a group G with a generating set S, a word in S is an arbitrary

product of elements of S and their inverses, and a reduced word in S is a word that

does not have any adjacent pair xx

−1

or x

−1

x, for all x ∈ S. 4

Notice that a word represents an element of G. Since S is a generating set in G, every

element of G can be represented by a word in S.

In 1911, the German American mathematician Max Dehn formulated the following three

fundamental problems for groups [5]:

Deﬁnition 1.1.4. In a group G with a given generating set S, the word problem is the

decision problem of determining whether two given words w

and w

in S represent the

same element of G. 4

Deﬁnition 1.1.5. In a group G with a given generating set S, the conjugacy problem

is the decision problem of determining whether two given words w

and w

in S are

conjugate. 4

Deﬁnition 1.1.6. The isomorphism problem is the decision problem of determining

whether two given ﬁnite group presentations deﬁne isomorphic groups. 4

1. BACKGROUND 14

Dehn was hoping to obtain general solutions to word and conjugacy problems for any

ﬁnitely presented group as well as a general solution to the isomorphism problem. It has

since been shown that the word and conjugacy problems are undecidable for some ﬁnitely

presented groups [15], and that the isomorphism problem is undecidable in general [1,16].

Note that solving the conjugacy problem is trivial on ﬁnite groups because given a

ﬁnite group G and two elements g

, g

∈ G, we can try out all the other h ∈ G to

determine whether there exists any relationship g

= hg

−1

. However, this algorithm will

not terminate on inﬁnite groups in the case where two elements are not conjugate. The

following example examines an inﬁnite group called a free group in which the conjugacy

problem is decidable.

Example 1.1.7. A group G is called free if it has a generating set S with no relations

between the generators. Note that every element in G can be written uniquely as a reduced

word in S. For example, if S = {x, y}, then the elements of G are all of the reduced words

involving x, x

−1

, y, and y

−1

A word is cyclically reduced if it is reduced and its ﬁrst and last elements are not

inverses of each other. We can cyclically reduce any reduced word by canceling all inverse

pairs from the beginning and the end. For example:

−1

yxy

−1

xxy

−1

x → yxy

−1

xxy

−1

→ xy

−1

Note that the resulting cyclically reduced word is conjugate to the original reduced word:

−1

yxy

−1

xxy

−1

x = (x

−1

y)(xy

−1

xx)(x

−1

If w

and w

are cyclically reduced words, it is not hard to show that w

and w

are

conjugate if and only if w

is a cyclic permutation of w

. For instance, xy

−1

xx is conjugate

to xxxy

−1

because

xxxy

−1

= (xx)(xy

−1

xx)(xx)

−1

1. BACKGROUND 15

Therefore, we can determine whether any two words are conjugate by cyclically reducing

them and checking whether the results are cyclic permutations of each other. It follows

that the conjugacy problem in free groups is decidable.

Given two strings s and t over an alphabet Σ, the string matching problem is the

problem of determining whether s is a substring of t. It has been proven by Knuth,Morris

and Pratt [12] that this problem is decidable in linear time in the length of the input

strings. By reducing the problem of checking whether two cyclically reduced words are the

same to the string matching problem, Madlener and Avenhaus [13] have shown that the

solution to the conjugacy problem in free groups is solvable in O(n), where n is the sum

of the lengths of the two input words in the free group. ♦

As we will see later in this paper, the solution to the conjugacy problem in Thompson’s

Group F proposed by [3] is similar to the solution shown above for free groups. Instead of

using reduced words, their solution begins by cyclically reducing strand diagrams. Next,

instead of checking whether the results are cyclic permutations of each other, they check

whether the resulting annular strand diagrams are isotopic (see Deﬁnition 1.2.11).

1.2 Directed Graphs Embedded on Surfaces

In this section, we discuss graphs on a surface S. For our purposes in this project, we

restrict our discussions to the following surfaces: the Euclidean plane R

, the sphere, the

unit square, and the annulus. While the sphere can be thought of as R

∪ {∞}, both the

unit square and the annulus are subspaces of the Euclidean plane.

Deﬁnition 1.2.1. A directed graph is a 4-tuple G = (V, E, s, t) where:

1. V is the set of vertices,

2. E is the set of directed edges,

3. the function s : E → V assigns a source vertex to each edge, and

1. BACKGROUND 16

4. the function t : E → V assigns a target vertex to each edge. 4

Notice that Deﬁnition 1.2.1 allows a directed graph to have one or more loops from a

vertex to itself as well as multiple distinct directed edges between the same source and

the same sink.

Deﬁnition 1.2.2. Let G = (V

, E

) and H = (V

, E

) be undirected graphs. Then, an

isomorphism of G and H is a pair (φ

, φ

) where:

1. φ

: V

→ V

is a bijection, and

2. φ

: E

→ E

is a bijection

such that an edge e ∈ E

connects vertices v

and v

in V

if and only if φ

(e) ∈ E

connects φ(v

) and φ(v

) in V

An isomorphism of two directed graphs G and H is an isomorphism (φ

, φ

) such

that the source of each edge e in G corresponds to the source of φ

(e) in H, and similarly

the target of e corresponds to the target of φ

(e). 4

Two graphs G and H are said to be isomorphic if there exists an isomorphism between

them. Intuitively, two isomorphic graphs can be thought of as similar graphs because they

have certain common properties. In particular, any property that is true for an object in

G and is preserved by the isomorphism is also true for its corresponding object in H.

For our purposes, we consider embeddings of graphs on surfaces. For the following

deﬁnition, a curve on a surface S is any continuous, one-to-one function γ : [0, 1] → S,

where γ(0) is the begin point and γ(1) is the end point of the curve.

Deﬁnition 1.2.3. An embedding of a directed graph G = (V, E, s, t) on a surface S is

an ordered pair (f, c) where:

1. f : V → S is one-to-one,

1. BACKGROUND 17

2. c = {c

}

e∈E

is a collection of curves on S, one for each directed edge, that do not

intersect except at their begin points and end points, and

3. if e ∈ E, then c

is a curve with begin point f(s(e)) and end point f(t(e)).

An embedded graph is a graph together with its embedding on some surface S. 4

In essence, an embedding of G on S is a visual representation or a drawing of G on S.

In such a drawing, vertices are represented by points on S, each directed edge is a curve

on S, and the directed edges are allowed to intersect only at common end vertices. Notice

that it is possible for a directed graph to have several diﬀerent embeddings on a surface.

Example 1.2.4. A planar graph is a graph that can be embedded on the plane. Fig-

ure 1.2.3 shows three diﬀerent embeddings of the same planar graph. ♦

We need a formal notion of what it means to move a graph around on a surface. In order

to formulate this notion, we need to understand what it means to move a curve around a

surface.

Deﬁnition 1.2.5. A homotopy of curves on a surface S is a family of curves {γ

}

τ ∈[0,1]

S such that the function f : [0, 1]×[0, 1] → S deﬁned by f(σ, τ ) = γ

(σ) is continuous. 4

Intuitively, a homotopy is a way of “continuously deforming” a curve on a surface. We

can think of τ as the time during the deformation, and for each value of τ corresponding

to a curve C, σ represents the spatial coordinates along the length of C (i.e., where a

point is on C). Observe that we are allowing the end points of a curve to move during the

homotopy. Thus, any two curves on the plane are homotopic.

Example 1.2.6. In Figure 1.2.1.(a), at τ = 0 the curve is

(σ) = (cos(πσ), sin(πσ)),

1. BACKGROUND 18

Τ=0

Τ=1

H1,0L

H-1,0L

H2,0L

H-2,0L

Curve A

Curve B

0.5

(a) a semicircular curve centered at (0,0) (b) Deformation of curve B into A

Figure 1.2.1. Homotopy of curves on the plane.

and at τ = 1 the curve is

(σ) = (2 cos(πσ), 2 sin(πσ)).

A homotopy for this semicircular curve is

{γ

(σ) = ((τ + 1) cos(πσ), (τ + 1) sin(πσ))}

τ ∈[0,1]

In (b), each of the curves represents a unique value of τ with σ continuously increasing

from 0 to 1. The blue, dashed curves show the deforming of curve B to curve A at discrete

values of τ, each leading to a unique γ

. The red crosses represent the pair (σ, 0) where

σ ∈ [0, 1] is unique for each red cross. The solid curve B corresponds to the range of

, and the range of γ

is the curve A. Thus, B is continuously deformed into A as τ is

increased from 0 to 1. ♦

Deﬁnition 1.2.7. An isotopy of directed graphs on a surface S is a family of embeddings

{(f

, c

)}

τ ∈[0,1]

of a directed graph G = (V, E, s, t) on S such that:

1. for each v ∈ V , τ 7→ f

(v) is continuous, and

2. for each e ∈ E, {(c

)

}

τ ∈[0,1]

is a homotopy of directed curves, where f

(s(e)) =

(0))

and f

(t(e)) = (c

(1))

. 4

Isotopy can be visualized as the continuous deformation of an embedding on a surface.

Notice that isotopy is a consequence of the continuous deformation of the points on the

1. BACKGROUND 19

Embedding E

Figure 1.2.2. Isotopy of graphs on the plane.

surface representing the vertices, and the curves on the surface representing the edges, of

the embedded graph. Figure 1.2.2 shows an isotopy of a directed graph on the plane.

Deﬁnition 1.2.8. Let E

and E

be two embeddings of a directed graph G on a surface

S. Then E

and E

are isotopic if there exists an isotopy (f

, c

)

τ ∈[0,1]

on S such that at

τ = 0 the embedding is E

, and at τ = 1 the embedding is E

. 4

Example 1.2.9. Figure 1.2.3 shows three embeddings A, B, and C of the same directed

graph on the plane. There is no way to move the vertices 1 and 4 in B into the circular

topological space between edges e

and e

. This shows that B is not isotopic to A and C.

Because vertex 1 in A cannot be moved into the region enclosed by edges e

, e

, and

, we can safely claim that A is not isotopic to C. Thus, none of these embeddings are

isotopic on the plane. ♦

Embedding A Embedding B Embedding C

Figure 1.2.3. A, B, and C are diﬀerent embeddings of the same planar graph. None of the

embeddings are isotopic on the plane, but B and C are isotopic on the sphere.

1. BACKGROUND 20

If two directed graphs are isomorphic, and one of the graphs has an embedding E on

a surface, obviously this gives an embedding of the other graph on the surface. Stated in

a diﬀerent way, we can “compose” the embedding E with the isomorphism to obtain an

embedding of the other graph. The following deﬁnition formalizes this notion.

Deﬁnition 1.2.10. Let G and G

be directed graphs. Let E = (f, c) be an embedding

of G on a surface S, and let φ = (φ

, φ

) be an isomorphism from G

to G. Then the

induced embedding of G

on S is E

= (f

, c

), where f

= f ◦ φ

and c

= c ◦ φ

. We

say that E

is the embedding of G

on S induced by φ. 4

We can use induced embeddings to deﬁne isotopy between two diﬀerent graphs on a

surface.

Deﬁnition 1.2.11. Let G and H be directed graphs with embeddings E

and E

respec-

tively on a surface S. Then G and H are isotopic on S if there exists an isomorphism

φ : G → H such that the induced embedding (E

◦ φ) is isotopic to E

on S. 4

Intuitively, we can think of two directed graphs G and H as isotopic on a surface if H

is the image of G under some continuous deformation on the surface.

We will now discuss a simple algorithm that determines whether two embedded graphs

are isotopic. This involves the notion of the rotation system.

Deﬁnition 1.2.12. Let G be a directed graph with vertex set V and with embedding E

on a surface S. For each vertex v ∈ V , let ρ

denote the counterclockwise order of the

edges connected to v. Then the set {ρ

| v ∈ V } is called the rotation system of the

embedding E on S. 4

We need to clarify two major points about this deﬁnition:

1. The term “counterclockwise order” means the cyclic ordering of the directed edges

connected to a vertex v. This is a cyclic ordering, i.e., linear ordering up to cyclic

1. BACKGROUND 21

permutation. Note that the word “counterclockwise” assumes some standard ori-

entation of the surface S. In particular, we cannot deﬁne a rotation system for an

embedding on a non-orientable surface.

2. Because our directed graphs can be multigraphs, they can have loops, which are

edges from a vertex to itself. We need to distinguish the two appearances of the edge

that forms a loop, that is, whether the edge comes into the vertex before it goes out,

or the opposite. In this case, we need to mark the two occurrences of the edge in the

counterclockwise order so that there is no ambiguity in the ordering.

In the example below, we use e

to mark the incoming edge in the loop, and e

out

mark the outgoing edge in the loop.

Example 1.2.13. In Figure 1.2.3, observe that on the sphere B can be deformed into

C by translating B to the northern hemisphere (think of it as the rear of the sphere)

and then “pulling” the loops e

and e

towards the southern hemisphere (the front of the

sphere). Then this deformed embedding of B will appear the same as the embedding C.

Therefore, B and C are isotopic to each other on the sphere.

The rotation systems of the three directed graphs are:

• A → {(e

, e

out

, e

), (e

, e

), (e

, e

), (e

out

, e

)}

• • B → {(e

out

, e

), (e

, e

), (e

, e

), (e

out

, e

)}

• C → {(e

out

, e

), (e

, e

), (e

, e

), (e

, e

)}

Notice that the rotation systems of B and C are exactly the same, but that of A is diﬀerent

because in the counterclockwise order of the edges around vertex 1 for A starting at edge

, the input edge into the loop precedes the output edge in the loop. The opposite happens

for vertex 1 of both B and C where the loop is directed counterclockwise and thus the

output edge precedes the input edge in the loop. Furthermore, the counterclockwise order

1. BACKGROUND 22

of the edges around vertex 3 in A is not an element of the rotation systems of B and

C. ♦

Theorem 1.2.14. Two embeddings of a connected directed graph on a sphere are isotopic

if and only if both embeddings induce the same rotation system.

The proof of this theorem follows from Theorem 3.2.4 and Corollary 3.2.5 in Section 3.3

in [14].

This theorem allows us to use rotation systems to check for isotopy of directed graphs

on the sphere. Thus, in Example 1.2.13 we can immediately conclude that embeddings B

and C are isotopic on the sphere because their rotation systems are the same. However,

they are not isotopic on the plane. This is because the outer region in B corresponds to the

inside region in C enclosed by edges e

and e

. Furthermore, neither B nor C is isotopic

to A on the sphere because the rotation system of A is diﬀerent from those of B and C.

Corollary 1.2.15. Let G and H be connected directed graphs embedded on the sphere.

Then G and H are isotopic if and only if there exists an isomorphism φ : G → H that pre-

serves the counterclockwise order of the edges connected to corresponding vertices between

G and H.

Note that the correspondence between the vertices are deﬁned by the isomorphism.

Preserving the order means that the rotation systems for the corresponding vertex sets

are the same.

1.3 Thompson’s Group F

Most of the deﬁnitions in this section can be found in [2] and [4]. Thompson’s Group

F is one of the three Thompson’s Groups, and it is a certain group of piecewise-linear

homeomorphisms of the interval [0, 1] under the operation function composition. We now

describe this group, provide a generating set for it, and show how its elements can be

1. BACKGROUND 23

represented in graphs called tree diagrams. For a thorough introduction to F , the reader

is encouraged to look into [4].

1.3.1 Dyadic Rearrangements

Deﬁnition 1.3.1. A dyadic subdivision is any subdivision of the interval [0, 1] obtained

by:

1. choosing whether to divide the interval in half,

2. if chosen, then dividing the interval in half, and for each of the resulting intervals,

looping back to step (1). 4

For example, {[0,

], [

, 1]} and {[0,

], [

, 1]} are dyadic subdivisions. Note

that {[0, 1]} is also a dyadic subdivision.

A standard dyadic interval is an interval of the form: [

k+1

], where k, n ∈ N and

k ≤ 2

−1. Therefore, all the intervals in a dyadic subdivision are standard dyadic intervals.

Moreover, a dyadic subdivision is the division of [0, 1] into standard dyadic intervals.

If d

and d

are two dyadic subdivisions having the same number of standard dyadic

intervals, then we can create a piecewise-linear homeomorphism f : [0, 1] → [0, 1] which

linearly maps each interval of d

onto a corresponding interval of d

. Then f is called a

dyadic rearrangement of [0, 1]. For instance, Figure 1.3.1 shows two dyadic rearrange-

ments.

Theorem 1.3.2. Let f : [0, 1] → [0, 1] be a piecewise-linear homeomorphism. Then f is a

dyadic rearrangement if and only if:

1. Each slope of f is a power of 2, and

2. Each breakpoint of f has dyadic rational coordinates

For the proof of this theorem, the reader is referred to [2].

1. BACKGROUND 24

14

12

34

12

34

78

(a) x

(b) x

Figure 1.3.1. Generators for Thompson’s Group F . The right half of x

is the same as x

Corollary 1.3.3. The set F of all dyadic rearrangements forms a group under function

composition.

The resulting group is called Thompson’s Group F.

Proposition 1.3.4. (also Theorem 1.3.9 in [2]) The two dyadic rearrangements x

and

generate the group F with presentation

, x

| x

= x

, x

= x

where x

= x

−1

, x

= x

−2

, and x

= x

−3

As mentioned in [2] and [4], this is a common presentation for F. Note that our algorithm

for the conjugacy problem in F only accepts input words in the generating set hx

, x

1.3.2 Tree Diagrams

We now show how certain graphs called tree diagrams can be used to describe elements

of F .

Proposition 1.3.5. Any dyadic subdivision d can be encoded into a ﬁnite rooted binary

tree T where:

1. the root of T represents the interval [0, 1],

2. each vertex of T is a standard dyadic interval,

1. BACKGROUND 25

Ò!ß

Ó Ò ß

"Ó

Ò ß

"Ó

Figure 1.3.2. The inﬁnite binary tree of standard dyadic intervals in [0, 1] (image taken

from [2]).

3. an edge of T is a pair of standard dyadic intervals (C, P ) such that C is either the

left half of P and we get a left edge, or the right half of P in which case we get a

right edge, and

4. each leaf of T is an interval in d.

Another way of stating this proposition is that all dyadic subdivisions correspond to

ﬁnite subtrees of the inﬁnite binary tree shown in Figure 1.3.2. Using this encoding, we

can identify any element of F as a pair of ﬁnite subtrees corresponding to the subdivisions

in the domain and the range respectively. Such a pair of subtrees makes up the tree

diagram for the element.

Example 1.3.6. The element x

is a piecewise linear function that maps intervals of the

subdivision D which has breakpoints {0,

, 1} onto the intervals of the subdivision R

which has breakpoints {0,

, 1}. The subdivision D and its corresponding subtree are:

1. BACKGROUND 26

Similarly, the subdivision R and its corresponding subtree are:

Therefore, the tree diagram for x

can be obtained by pairing these two trees as shown

below:

Note that the two trees are arranged in a way such that the corresponding leaves are

vertically aligned. By convention, we place the subtree representing the domain above the

subtree representing the range (all images in this example have been taken from [2]). ♦

1.4 Strand Diagrams

output

left

input

right

input

left

output

right

output

Figure 1.4.1. A strand diagram, a merge, and a split (image taken from [3]).

In this section, we introduce a certain type of planar, directed graphs called strand

diagrams, which are derived from the tree diagrams that we described in Section 1.3.2.

Moreover, previous research by Belk and Matucci [3] shows that in each Thompson’s

1. BACKGROUND 27

Group there exists a solution to the conjugacy problem that involves strand diagrams,

and our algorithm for the conjugacy problem in F also uses strand diagrams.

Deﬁnition 1.4.1. A strand diagram is a ﬁnite acyclic digraph embedded on the unit

square with the following properties:

1. The graph has a source along the top edge of the square having an outgoing edge,

and a sink along the bottom edge with an incoming edge.

2. Any other vertex is:

(a) either a merge that has two incoming edges and one outgoing edge, or

(b) a split that has one incoming edge and two outgoing edges (see Figure 1.4). 4

Two isotopic strand diagrams are considered equal by convention.

A strand diagram corresponding to an element of F can be produced by gluing the

domain and the range subtrees of the element at their corresponding leaves and making

the edges directed from the domain subtree towards the range subtree. For instance,

Figure 1.4.2 shows how the strand diagram corresponding to x

can be obtained.

Our implementation uses the generating set hx

, x

i to create words for elements of F .

Figure 1.4.3 shows the strand diagrams for the generators. Notice that the strand diagram

for x

−1

can be produced by reversing the edge directions in the strand diagram for x

and

then ﬂipping the resulting strand diagram vertically. In general, given the strand diagram

Figure 1.4.2. Construction of the strand diagram for x

from its tree diagram (image taken

from [3]).

1. BACKGROUND 28

(a) x

(b) x

−1

(d) x

−1

Figure 1.4.3. Generators for F and their inverses.

S for an element f ∈ F , the strand diagram for f

−1

can be obtained by reversing all the

edge directions in S, and then ﬂipping S vertically.

1.4.1 Strand Diagram Manipulations

We now describe certain operations that are used to modify strand diagrams in our algo-

rithm for the conjugacy problem in F .

Deﬁnition 1.4.2. A reduction of a strand diagram is a simpliﬁcation of the strand

diagram using one of the two moves shown in Figure 1.4.4. We say that a strand diagram

has been reduced if no reductions can be performed on it. 4

Notice that a type II reduction move is possible whenever there exists an edge from a

merge to a split.

Deﬁnition 1.4.3. The concatenation of two strand diagrams s

and s

is the strand

diagram created by by gluing the sink of s

to the source of s

and then removing the

resulting vertex of degree 2. In this case, we say that s

has been concatenated to s

. 4

Figure 1.4.4. The two reduction rules (image taken from [3]).

1. BACKGROUND 29

f x

◦ f x

◦ f (reduced)

Figure 1.4.5. Composing elements of F by concatenating their strand diagrams. Note that

the concatenation makes a type II reduction move possible around the vertex v

(image

taken from [3]).

Concatenation of strand diagrams is equivalent to composition of corresponding ele-

ments in F .

Example 1.4.4. Figure 1.4.5 shows the concatenation of two elements f and x

, which

produces the strand diagram for the element x

◦ f , which has word x

f. Notice that a

concatenation immediately gives rise to a type II reduction move at the point of concate-

nation. ♦

The following theorem shows that the construction of a strand diagram is linear in

the length of the corresponding word, and it plays a signiﬁcant role in proving that our

algorithm for the conjugacy problem in F is linear.

Theorem 1.4.5. Let n be the length of the input word in the generating set hx

, x

i for

a strand diagram S. Let V

and E

be the number of vertices and edges respectively in S.

Then V

+ E

≤ 15n + 3.

Proof. Let the input word for S have length n. We will prove the theorem using induction

on n.

Base Case: Let n = 0. Then S is the strand diagram for the identity, which has a

source, a sink, and an edge connecting them. Thus V

+ E

= 2 + 1 = 3 ≤ 3.

1. BACKGROUND 30

Inductive Case: Assume that for a strand diagram S corresponding to a word of length

n, we have V

+ E

≤ 15n + 3.

Let S

be a strand diagram for an input word w, of length n + 1. By the inductive

hypothesis, for the word with the ﬁrst n characters in w, there exists a strand diagram S

such that V

+ E

≤ 15n + 3. Let g be the strand diagram for the (n + 1)th element in w.

Observe that g ∈ {x

, x

−1

, x

−1

}. We can create S

by concatenating g to S. We have

two cases to consider.

Case 1: g = x

or g = x

−1

. Then V

= 6 and E

= 7. Since concatenation removes 2

vertices and 1 edge, we have

+ E

= V

+ E

+ V

+ E

− 2 −1 = 15n + 3 +6+7 − 2 − 1 = 15n +13 ≤ 15(n+ 1) + 3.

Case 2: g = x

or g = x

−1

. Then V

= 8 and E

= 10. Again, since concatenation

removes 2 vertices and 1 edge, we have

= V

−2−1 = 15n +3 +8 +10 −2 −1 = 15n +18 ≤ 15(n +1)+3.

It follows that V

+ E

≤ 15(n + 1) + 3.

Annular Strand Diagrams

Recall that our algorithm for the conjugacy problem in F involves the use of strand

diagrams. To be more precise, the solution proposed by Belk and Matucci [3] is directly

based on the manipulation of certain directed graphs called annular strand diagrams,

derived from strand diagrams.

In this chapter, we discuss annular strand diagrams, provide the solution to the conju-

gacy problem in F [3] that involves modifying and comparing these graphs, and describe

the strategies we use to dynamically monitor the structure of mutating annular strand

diagrams, with particular emphasis on the decomposition into multiple connected compo-

nents.

2.1 Closing Strand Diagrams

We can close any strand diagram embedded on the unit square by making the output

from the parent of its sink the input to the child of its source, and then removing the

source and the sink. This turns the strand diagram to a graph embedded in an annulus,

called an annular strand diagram. One such example is shown in Figure 2.1.1.

2. ANNULAR STRAND DIAGRAMS 32

Figure 2.1.1. Annular strand diagram for x

obtained by closing its strand diagram

Deﬁnition 2.1.1. An annular strand diagram is a ﬁnite directed graph embedded in

the annulus, with the following properties:

1. Each vertex is either a merge or a split

2. Every directed cycle winds counterclockwise around the central hole. 4

Although we have deﬁned an annular strand diagram as a directed graph, it can have

free loops, which are directed cycles without any vertices. From property (2) in Deﬁni-

tion 2.1.1, it follows that every free loop winds counterclockwise around the central hole

of the annulus. Because free loops do not have end vertices, they are not allowed to be

present in directed graphs, however, they can exist in annular strand diagrams.

2.2 Reductions

Annular strand diagrams can be reduced using the three reduction moves shown in Fig-

ure 2.2.1. The third move merges two consecutive free loops with no vertices in the region

III

Figure 2.2.1. The reduction moves for annular strand diagrams. A type I move is allowed

when the shaded region is a topological disk. A type III move is allowed when the space

between the two free loops is a topological annulus containing no vertices (image taken

from [3]).

2. ANNULAR STRAND DIAGRAMS 33

Figure 2.2.2. A type I move reduces the central annular strand diagram to a free loop,

but a reduction II creates two concentric free loops. A reduction III on the diagram in the

right merges the two free loops, preserving unique normal forms (image taken from [3]).

between them into one free loop. This move is required to make reductions of annular

strand diagrams conﬂuent so that every annular strand diagram reduces to a unique re-

duced annular strand diagram, as shown in the following example.

Example 2.2.1. The central annular strand diagram in Figure 2.2.2 is subject to both

type I and type II moves, but the two moves produce diﬀerent annular strand diagrams.

A type III move reconciles the results, ensuring that the central annular strand diagram

reduces to a unique normal form. ♦

Example 2.2.2. Figure 2.2.3 shows an annular strand diagram and the reductions applied

to it until it reduces to a free loop. Notice that a type II move on (a) splits the connected

annular strand diagram into two connected components. The reductions applied to (d)

demonstrate that both type I and type II moves in annular strand diagram can result in

the formation of free loops. ♦

At this point we are prepared to comprehend the solution to the conjugacy problem in

F proposed by [3]. The solution, summarized in Theorem 2.2.3, involves reducing annular

strand diagrams and checking for isotopy.

2. ANNULAR STRAND DIAGRAMS 34

see

line

(a) an annular strand diagram, (b) splits into two components after

some type II moves,

Figure 2.2.3. Reducing an annular strand diagram. In the pictures, the green regions are

subject to type I moves, and the red and blue regions are each subject to type II moves.

The type II move on the red region in (a) breaks the connected annular strand diagram

into two connected components.

Theorem 2.2.3. (Belk and Matucci). Let g and h be elements of Thompson’s group

F . Let G and H be strand diagrams for g and h, and let G

and H

be the reduced an-

nular strand diagrams obtained by closing G and H and then reducing. Then g and h are

conjugate if and only if G

and H

are isotopic.

For the proof of this theorem, the reader is referred to [3]. As will be shown in the

next chapter, our algorithm for the conjugacy problem in F fundamentally builds on this

theorem. The rest of this chapter provides insights into the structure of annular strand

2. ANNULAR STRAND DIAGRAMS 35

diagrams and explains the strategies we employ to keep track of the conﬁguration of an

annular strand diagram before, during, and after it is reduced.

2.3 Concentric Components

Reduced annular strand diagrams can have multiple connected components. In this sec-

tion, we discuss how annular strand diagrams can decompose into two or more connected

components during reductions, showing that directed cycles and type II reduction moves

are directly responsible, and we also provide further insights into the structure of these

connected components.

Proposition 2.3.1. In any strand diagram, there is a directed path from every vertex to

the sink.

Proof. Let S be a strand diagram. Assume that there exists a vertex v ∈ S such that

there is no directed path from v to the sink. Construct a directed path P by arbitrarily

following an outgoing edge from v to a vertex v

∈ S which cannot be the sink. Expand P

by following an arbitrary outgoing edge of v

to another vertex v

∈ S which is again not

the sink. Create an inﬁnite path by repeatedly keep expanding P in this manner. Because

S has ﬁnitely many vertices, the inﬁnite path P must have a cycle. But S is acyclic, which

contradicts the assumption that P has a cycle. Hence, P must be a directed path from v

to the sink.

Proposition 2.3.1 leads immediately to the following corollary.

Corollary 2.3.2. All strand diagrams are connected.

Since closing any strand diagram only “glues” the source and the sink, it follows that

closing does not split a strand diagram into two components. Thus, any annular strand

2. ANNULAR STRAND DIAGRAMS 36

diagram produced by closing a strand diagram is connected. Note that closing the strand

diagram for the identity produces a free loop.

However, a sequence of reductions can sometimes change the number of connected com-

ponents in an annular strand diagram. Observe that closing any strand diagram creates a

directed cycle, and an edge which is an output of a merge and an input to a split. Therefore

any annular strand diagram produced by closing a strand diagram is immediately subject

to a type II reduction move. As we have seen in Figure 2.2.3, reductions on annular strand

diagrams can result in the formation of multiple components as well as the merging of

multiple connected components. In particular, a type II move can split a connected annu-

lar strand diagram into two components if the edge from the merge to the split involved

in the reduction is the intersection of two directed cycles, as shown in Figure 2.3.1. Such

a reduction disconnects the strand diagram, making the cycles disjoint, and creating two

components. Furthermore, a reduction III move can merge two connected components into

one. Because reducing an annular strand diagram can modify the number of connected

components, we must keep track of the order of these components in order to correctly

construct the reduced annular strand diagram.

Figure 2.3.1. A reduction II move causing a connected component to split into two (each

shaded region represents a component).

2. ANNULAR STRAND DIAGRAMS 37

(connected) A

(disconnected)

Figure 2.3.2. Two reduced annular strand diagrams (A

has been taken from [3]).

We will use the following terminologies to describe certain cycles in annular strand

diagrams:

• split loop - a directed cycle which has only splits

• merge loop - a directed cycle which has only merges

Example 2.3.3. Figure 2.3.2 shows two reduced annular strand diagrams A

and A

. A

is a connected graph having a merge loop as the inner and the outermost directed cycles,

and a split loop between them. Consecutive directed cycles in A

are connected by trees

(colored blue). A

has three components, where the second component is a free loop. The

two directed cycles in the ﬁrst component in A

are connected by reduced strand diagrams

(colored blue). Excluding the free loop, the directed cycles (colored black) in both A

and

are either merge loops or split loops. ♦

Proposition 2.3.4. In any reduced annular strand diagram R:

1. Each component C has at least one directed cycle.

2. Each directed cycle is either a split loop, a merge loop, or a free loop.

3. No directed cycle intersects another directed cycle or itself.

4. Every component surrounds the inside hole of the annulus.

2. ANNULAR STRAND DIAGRAMS 38

Proof.

1. Observe that if C is a free loop, then it has a directed cycle. Now assume that C

is not a free loop. Observe that each vertex in C has at least one output edge. In

C, construct an inﬁnite path P using the same inﬁnite path construction method

discussed in Proposition 2.3.1. Because C has ﬁnitely many vertices, eventually in

P a vertex v

will be repeated. Then the path P has a directed cycle starting at v

2. Assume that there exists a directed cycle with merges and splits. Then there must

be at least one merge with an outgoing edge to a split. It follows that R can still

undergo a reduction II move, which is a contradiction since R is already reduced.

3. Assume that two directed cycles intersect. Then the cycles must intersect at a merge

and then split apart, leading to a reduction II move, which is a contradiction since

R is already reduced. By using the same argument, we can show that a directed

cycle cannot intersect itself.

4. Because every component has at least one directed cycle D, and since every directed

cycle annular strand diagram winds counterclockwise around the inside hole (see

part (2) of Deﬁnition 2.1.1), it follows that D must go around the inside hole of the

annulus. Therefore, each component surrounds the inside hole.

Therefore, any reduced annular strand diagram has a ﬁnite number of disjoint directed

cycles winding counterclockwise around the central hole. Furthermore, consecutive directed

cycles in a connected component are held together by acyclic directed planar subgraphs,

consisting of splits and merges.

Proposition 2.3.5. In each component C with two or more directed cycles in a reduced

annular strand diagram, these cycles alternate concentrically between split loops and merge

loops.

2. ANNULAR STRAND DIAGRAMS 39

Proof. Let L and L

be two concentric directed cycles in C. Assume without loss of gener-

ality that L is a split loop in C. Observe that for each split v in L, there exists an outgoing

edge that is not part of L. Since L and L

are concentric and since they are present in the

same component C, there must be at least one edge e emanating from L into the annular

region between L and L

. Using the split v ∈ L which has the edge e as an output, con-

struct an inﬁnite path P starting at e using the same inﬁnite path construction method

discussed in Proposition 2.3.1. Because C has ﬁnitely many vertices, eventually in P a

vertex v

will be repeated. It follows that the path P has a directed cycle D 6= L starting

at v

. Either D = L

or L

is between L and D, and since L and L

are concentric, in both

cases it follows that P must have hit at least one vertex v

∈ L

. But then v

has another

edge that is part of the directed cycle L

. It follows that v

is a merge, and therefore L

must be a merge loop.

The case when L is a merge loop can be proved using a similar reasoning as above, and

we omit its details.

We have obtained deeper insights into the structure of connected components in an-

nular strand diagrams. In an annular strand diagram, the connected components are in

concentric order in the annulus, and each component is itself an annular strand diagram.

A component with exactly one directed cycle must be a free loop. For each component

excluding the free loop:

1. there exist at least two directed cycles,

2. the entire component lies in the annular region between its innermost and outermost

directed cycles.

This means that given an annular strand diagram A in the annulus, any straight line L

drawn from the inside of the annulus to the outside ﬁrst intersects an edge that is part of

the innermost directed cycle in A, and L crosses the remaining directed cycles in concentric

2. ANNULAR STRAND DIAGRAMS 40

order until it reaches the outside of the annulus. The last edge crossed by L is an edge in

the outermost directed cycle in A.

2.4 The Cutting Path

In this section, we describe our strategy to keep track of the ordering of components in an

annular strand diagram. Our approach involves having a dynamic ordered list of some of

the edges in the annular strand diagram, and for this purpose we use the cutting path.

Deﬁnition 2.4.1. A cutting path, in an annular strand diagram A, is a directed path

from the inside hole of the annulus all the way to the outside such that it crosses at least

one edge of A, and the edge crossing rules in Figure 2.4.1 hold. 4

Theorem 2.4.2. Each annular strand diagram obtained by closing a strand diagram has

a cutting path, and its corresponding reduced annular strand diagram also has a cutting

path.

Proof. Let S be a strand diagram and let A be the annular strand diagram obtained

by closing S. It follows that A has a cutting path P which crosses the edge created

during closing (see Figure 2.4.3). Perform all possible reductions on A, and during each

Cutting Path

Edge in Annular

Strand Diagram

ALLOWED

Cutting Path

Edge in Annular

Strand Diagram

NOT ALLOWED

Figure 2.4.1. For a cutting path, the edge crossing in (a) is allowed and (b) is not allowed

2. ANNULAR STRAND DIAGRAMS 41

reduction, if P goes through a region of reduction as shown in Figure 2.4.2, then update

P as described below.

• Reduction I: P does not need to be updated if it goes through e

or e

since the

reduction will merge these edges accordingly. If P goes through the shaded disk, it

must enter the disk by crossing e

and leave by crossing e

. In this case, replace e

and e

in P with e

(same as e

• Reduction II: Again P does not require an update if it crosses all the other edges

except e

since these edges will be modiﬁed by the reduction itself. If P goes through

, then after performing the reduction, it must go through the edge e

(same as e

)

before the edge e

(same as e

• Reduction III: Replace the two free loops in P with the new free loop.

Note that it is possible that P crosses more than once an edge which is involved in a

reduction, but this is not a problem if we use the same rule to update edges in P for all

such crossings. Observe that updating P during a reduction move does not violate the

edge crossing rules for a cutting path. Therefore, when A is reduced, it has the cutting

path P .

Example 2.4.3. Figure 2.4.3 shows the edges in an annular strand diagram that the

cutting path intersects before and after the annular strand diagram is reduced. ♦

III

(a) reduction I (b) reduction II (c) reduction III

Figure 2.4.2. Update of the cutting path for each reduction move.

2. ANNULAR STRAND DIAGRAMS 42

(a) (b) (c)

Figure 2.4.3. Status of a cutting path (a) after closing a strand diagram (crosses edge e

(b) after performing a type II reduction, and (c) after the annular strand diagram is

reduced. The numbers denote the order of the edges in the cutting path

The following proposition gives an important insight into how a cutting path can identify

the concentric order of components in a reduced annular strand diagram.

Proposition 2.4.4. Let C

, ..., C

be the components of a reduced annular strand diagram

A in concentric order. Let e

, ..., e

be the sequence of edges crossed by a cutting path P .

Then e

, ..., e

consists of one or more edges from C

followed by one or more edges from

and so forth, ending with one or more edges from C

Proof. Observe that the ﬁrst edge that P intersects must be part of the innermost directed

cycle in A. It follows that e

∈ C

Because all the directed cycles in A are directed counterclockwise, if P has already

crossed an edge in such a directed cycle d, then it cannot cross an edge in d in the

opposite direction due to the edge crossing rules in Figure 2.4.1. As a result, P must go

through every directed cycle exactly once, and P must cross the directed cycles in A in

concentric order from the central hole to the outside of the annulus.

Every component has an innermost cycle and an outermost cycle (which are the same

for a free loop). Therefore, for each component C

, the ﬁrst edge P crosses is part of the

innermost cycle, and P keeps crossing edges in C

until it crosses the outermost cycle. Once

P leaves the outermost cycle of C

, it cannot get back into C

because of the edge crossing

2. ANNULAR STRAND DIAGRAMS 43

rules for a cutting path. Therefore, P is not allowed to re-enter a connected component

which it has already entered once, and this forces P to continue to enter the concentric

components in order until it exits the annulus.

It follows that by keeping track of:

• the order of the edges the cutting path meets, and

• the connected components to which these edges belong,

the cutting path allows us to identify the concentric ordering of components in any annular

strand diagram, with very little computation and storage. Knowledge of the sequence

of connected components is essential for checking whether two reduced annular strand

diagrams are isotopic.

2.5 Isotopy of Reduced Annular Strand Diagrams

As proven by Belk and Matucci [3], two elements of F are conjugate if and only if their

corresponding reduced annular strand diagrams are isotopic (see Theorem 2.2.3). Hence,

our solution algorithm for the conjugacy problem in F must be able to deduce whether

two reduced annular strand diagrams are isotopic. In this section, we describe the term

isotopy in the context of annular strand diagrams.

Recall from Deﬁnition 1.2.12, in an embedding of a directed graph, the rotation system

is the family of the counterclockwise order of the edges connected to each vertex. For

an annular strand diagram, knowing the counterclockwise order of the edges connected

to a merge is the same as knowing the left and right inputs, and similarly the left and

right outputs in the case of a split. This constitutes a rotation system for annular strand

diagrams.

2. ANNULAR STRAND DIAGRAMS 44

The following theorem has a signiﬁcant role in the design of our algorithm for the

conjugacy problem in F . However, its proof is beyond the scope of this project, so we

provide an outline of the proof and leave it to the reader to ﬁgure out the missing details.

Theorem 2.5.1. Two connected annular strand diagrams A

and A

are isotopic in the

annulus if and only if there exists a directed graph isomorphism between them that preserves

the rotation system.

Sketch of Proof. Observe that the annulus is a sphere with two holes in it:

1. the inner hole at (0,0), and

2. the outer hole at ∞.

It is not diﬃcult to see that two directed graphs G and H are isotopic in the annulus if

and only if:

1. G and H are isotopic on the sphere, and

2. the inner and outer holes respectively lie in corresponding faces in G and H.

When G and H are connected annular strand diagrams, observe that their faces containing

inner and outer holes are the only faces whose boundaries are directed cycles. Moreover, the

directed cycle surrounding the inner hole goes counterclockwise and the one surrounding

the outer hole goes clockwise (since it appears counterclockwise on the plane).

Therefore, A

and A

are isotopic in the annulus if and only if they are isotopic on the

sphere. But by Corollary 1.2.15, we know that two connected annular strand diagrams

are isotopic on the sphere if and only if there exists a directed graph isomorphism that

preserves the rotation system.

Corollary 2.5.2. If two connected annular strand diagrams A

and A

represent diﬀerent

embeddings of the same directed graph, and they agree for:

1. every merge on the left and right inputs, and

2. ANNULAR STRAND DIAGRAMS 45

2. every split on the left and right outputs,

then A

and A

are isotopic.

In other words, isotopy preserves the direction of the edges in addition to isomorphism.

For instance, in the case of two isotopic annular strand diagrams G and H, the left output

of a vertex in G corresponds to the left output of the corresponding vertex in H mapped

by the isomorphism. Furthermore, the counterclockwise order of input(s) and output(s) of

a vertex in G is the same as the counterclockwise order of input(s) and output(s) of the

corresponding vertex in H.

Example 2.5.3. Figure 2.5.1 shows three reduced annular strand diagrams A

, A

, and

. Observe that A

can be obtained by applying a 180

◦

rotation to A

on the annulus.

Vertex v

∈ A

would fall over vertex v

, and a depth ﬁrst search from these corre-

sponding vertices will conﬁrm the presence of an isotopy. On the other hand, A

is not

isotopic to the A

or A

. Observe that the left output from the left split in the tree in A

has target v

, which has an outgoing edge to the outermost directed cycle. However, the

left output from the left split in the tree in A

has a target vertex, which has an outgoing

edge to the innermost directed cycle. Similarly, A

is not isotopic to A

. ♦

Figure 2.5.1. Three reduced annular strand diagrams in which A

and A

are isotopic.

2. ANNULAR STRAND DIAGRAMS 46

Corollary 2.5.4. Given two reduced annular strand diagrams G and H, where C

, g

, ..., g

} and C

= {h

, h

, ..., h

} are the sets of connected components in G and

H respectively in concentric order from the inside of the annulus to the outside, then G

and H are isotopic if:

1. n = m, and

2. g

∈ C

and h

∈ C

are isotopic for each i ∈ {1, 2, ..., n}.

Algorithm for the Conjugacy Problem in F

In this chapter, we provide a comprehensive description of our algorithm for the conjugacy

problem in F, the biggest contribution in our research. We discuss our implementation

called ConjugacyF, with particular emphasis on key notes in each major step of the

algorithm, and analyze our solution algorithm to show that theoretically it executes in

O(n), where n is the sum of the lengths of the input words. We provide a tested, bug-free

Java implementation of ConjugacyF, showing evidence of correctness using our results,

and describe the user interface towards the end of this chapter.

The theoretical implementation reduces the problem of checking whether two reduced

annular strand diagrams are isotopic to the problem of determining whether two planar

graphs are isomorphic. It uses the O(|V |) algorithm proposed by [10] for the isomor-

phism problem in planar graphs, where |V | is the number of vertices in the input planar

graphs. However, as stated by the authors in [10], their algorithm is mainly theoretical and

too complicated to be implemented. Due to this reason, ConjugacyF directly determines

whether two reduced annular strand diagrams are isotopic, and as a result, it executes in

O(n

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 48

Theorem 3.0.5. Given two input words w

and w

in hx

, x

i representing elements of F,

the proposed algorithm for the conjugacy problem decides whether w

and w

are conjugate

in O(n), where n = |w

| + |w

The rest of this chapter proves this theorem. We emphasize that this theorem uses the

O(|V |) algorithm proposed by [10] for the isomorphism problem in planar graphs.

3.1 Algorithm Overview

In this section, we describe the major steps in the ﬂow of the algorithm. A ﬂowchart for

the algorithm is shown in Figure 3.1.1, and the steps are highlighted below:

1. The algorithm takes as input two words w1 and w2 in the generating set hx

, x

Hence, an input word is a string with a sequence of characters from the set

, x

−1

, x

−1

2. The strand diagrams for these words are constructed, and they are closed to obtain

the corresponding annular strand diagrams (Section 3.3).

3. The annular strand diagrams are reduced (Section 3.4).

4. The connected components in each reduced annular strand diagram are labeled and

stored in a list in concentric order from the inside of the annulus to the outside

(Section 3.5).

5. For each reduced annular strand diagram, the components are encoded to planar

graphs, which are stored in lists in the same concentric order as that of the compo-

nents (Section 3.6).

6. Then the following procedure determines whether w1 and w2 are conjugate:

Let P

= {g

, g

, ..., g

} and P

= {g

, g

, ..., g

} be the lists of planar graphs for

the elements w1 and w2 respectively. If n 6= m, then w1 and w2 are not conjugate.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 49

Strand Diagram

Creator

Annular Strand Diagram

Creator (i.e. Closing)

Reduce Connected Component Labeling

Encoding to Planar Graph

Return True if conjugate,

otherwise return False

Isomorphism

Checker

Figure 3.1.1. Overview of the solution algorithm for the conjugacy problem in F

Otherwise, for each i ∈ {1, 2, ..., n}, the algorithm checks whether g

and g

are

isomorphic. If all such g

and g

are isomorphic, then w1 and w2 are conjugate, and

not conjugate otherwise (Section 3.8).

In accordance with the sections mentioned above, the other major topics in this chapter

are organized as follows:

Section 3.2 describes the data structure; Sections 3.6 - 3.7 prove an important theorem

relating isotopy of strand diagrams to isomorphism of planar graphs; Section 3.9 describes

the subroutine in our Java program that compares the rotation systems of annular strand

diagrams to determine whether they are isotopic, proving that this subroutine causes the

running time of ConjugacyF to be quadratic; Section 3.10 analyzes the results we obtained

using ConjugacyF and provides evidence to show that the implementation is bug-free; and

ﬁnally Section 3.11 describes the software we created for the conjugacy problem in F using

Java, with details on how to use the interface.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 50

Furthermore, any section where part of the solution algorithm is discussed also presents

an analysis of that part of the algorithm towards proving that the overall algorithm is

linear in the length of the input words.

3.2 The Data Structure

3.2.1 Background: Doubly Linked Lists

To minimize the running time of the solution algorithm, on several occasions we use the

doubly linked list data structure. For a broader description of doubly linked lists, the

reader is referred to [17].

Deﬁnition 3.2.1. A doubly linked list is a data structure containing sequentially linked

nodes, each of which has:

• a data ﬁeld holding a value,

• a previous ﬁeld that refers to the previous node, and

• a next ﬁeld that refers to the next node

in the sequential ordering of nodes in the data structure. 4

Conventionally, the previous ﬁeld of the beginning node and the next ﬁeld of the ending

node are set to null. Discussed below are certain methods that our solution algorithm

will invoke on a customized doubly linked list D. Note that all these methods take constant

time.

• add(<Type> a): creates a new node N containing a, and attaches N at the end of D.

• addAfter (<Type> a, <Type> b): creates a new node N containing b, inserts N

between the node p holding a and the node p+1, and creates new links between p,N,

and p+1.

• remove(Node N): removes N from D and and links its previous node to its next node.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 51

• remove(<Type> a): inquires the node ﬁeld of a to ﬁnd the node in which a belongs

in D. Then removes this node, and links its previous node to its next node.

• replace(<Type> a, <Type> b): creates a new node N containing b, substitutes the

node holding a with N, thus replacing the data a with the data b in D.

Note that it is important that the above operations each take constant time for Con-

jugacyF to execute in linear time. However, our Java implementation of ConjugacyF uses

the in-built LinkedList data structure for Java, which may not allow these operations in

constant time.

We now describe the data structure (as a Java model) for representation and manipu-

lation of strand diagrams and annular strand diagrams. Recall that strand diagrams for

elements of F have four kinds of vertices:

• a merge, which has two parents and one child

• a split, which has one parent and two children

• a source of degree 1, with an outgoing edge to a split, and

• a sink of degree 1, with an incoming edge from a merge

The source and the sink are involved only in concatenations (see Section 1.4.1) and

closing (see Section 2.1) . Annular strand diagrams have only merges and splits as vertices.

Note 3.2.2. All the linked lists in our data structure are doubly linked lists with constant

time access. ♦

3.2.2 Class: Edge

1. Each Edge object is directed from a source vertex to a target vertex.

2. Each Edge object has a unique ID.

3. The ﬁeld class is an array of two integers that records the class to which the edge

belongs (see Section 3.6 for discussion of “class”). In this array, the ﬁrst integer

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 52

Figure 3.2.1. The Java model of the data structure used for the solution to the conjugacy

problem in F . Note that all the linked lists are doubly linked.

denotes the input type and the second integer denotes the output type for the edge.

These integers can be the following:

• 0 → free loop

• 1 → left input or left output

• 2 → right input or right output

4. ConjugacyF involves insertion of edges into a linked list called cuttingPath, which

stores a dynamic subsequence of edges in the order in which they meet a particular

cutting path (see Section 3.2.5). The ﬁeld node for an Edge object stores the container

node that holds the edge, if present, in cuttingPath, otherwise node is set to null.

5. The ﬁeld flagged is required to mark edges during connected component labeling

of reduced annular strand diagrams (discussed in Section 3.5).

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 53

6. Invoking the method makeFreeLoop() turns the edge into a free loop by setting

isFreeLoop to true, both elements of class to 0, and making the source and the

target vertices null.

7. Given an edge e

with source vertex s, the combineEdge() method (see Algorithm 7

in the Appendix takes another edge e

with target vertex t as input, and then merges

the two edges. As a result, both e

and e

are the same edge with source vertex s,

target vertex t, class[0] from old e

, class[1] from old e

, and:

• if both their node ﬁelds are null, then a fake Node having an empty data ﬁeld

is constructed for e

, and the node for e

is also assigned this Node.

• if neither of their node ﬁelds are null, then the node for e

is destroyed ﬁrst,

and then assigned the node for e

• if exactly one of the edges has a node that is not null, then the other edge has

its node set to the former’s node.

Note 3.2.3. In the description of the solution algorithm, for any Edge object e, if e.node

is null, then e.node is an unassigned or it is a fake Node. ♦

3.2.3 Class: Vertex

1. We use the ﬁeld type to denote the vertex type, which can be any string in the

set {source, sink, merge, split}. Note that each Vertex object has four Edge objects

associated with it. Using the type ﬁeld, we can safely decide which of these Edge

objects are allowed for a vertex, as shown in Table 3.2.1.

By convention, a vertex having a lone input edge has the edge stored in

leftParentEdge, and a vertex having a lone output edge has the edge stored in

leftChildEdge. By inquiring the associated Edge objects, the children and parents

of any vertex can be found, which are provided by the getter methods.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 54

2. Each vertex has a unique ID, required for creating and copying strand diagrams.

3. In (annular) strand diagrams, vertices will be stored in a linked list. In order to

remove vertices from this linked list in constant time during reductions, the container

node in which a vertex belongs is stored in the node for Vertex objects.

4. As will be shown later, during reductions, split vertices may be put into a stack

called stackReduceSplits in the Annular class, and the ﬁeld inStack is used to

tell whether a vertex is currently on this stack.

5. During the isotopy check discussed in 3.9, each vertex in an annular strand diagram

will have its isPaired ﬁeld set to true when its corresponding vertex in the other

annular strand diagram has been assigned, and the correspondent ﬁeld is used to

hold this corresponding vertex.

Note 3.2.4. The Vertex data structure preserves the counterclockwise order of the edges

since it keeps track of the left and right parents of a merge, and similarly the left and the

right children of a split. ♦

3.2.4 Class: Graph

The Graph data structure is used to hold planar graphs that are generated from reduced an-

nular strand diagram components using the encoding algorithm (discussed in Section 3.6).

A list of the vertices and a list of the undirected edges are suﬃcient to represent planar

graphs. In the solution algorithm, Graph objects will be compared to determine whether

leftParentEdge rightParentEdge leftChildEdge rightChildEdge

source 7 7 3 7

target 3 7 7 7

merge 3 3 3 7

split 3 7 3 3

Table 3.2.1. The Edge objects associated with certain vertex types.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 55

they are isomorphic in order to decide whether two reduced annular strand diagrams are

isotopic (see Theorem 3.7.1).

3.2.5 Class: Strand

This data structure represents elements of F in strand diagram forms.

1. We construct a Strand object, representing a strand diagram, from its input word,

which is a string in the generating set hx

, x

2. We store the source and the sink vertices so that concatenations and closing can

be performed in constant time.

3. As each Vertex object stores the counterclockwise order of edges connected to it, the

ﬁeld vertices, holding all the vertices in a strand diagram, has suﬃcient information

to correctly construct the strand diagram.

4. stackReduceSplits is a stack that stores a list of split vertices during concatena-

tions (discussed in Section 3.3).

5. The method concatenate() performs concatenation of two Strand objects (see

Algorithm 8).

6. Invoking the method close() on a Strand object turns it into an Annular object

that represents the corresponding annular strand diagram.

3.2.6 Class: Annular

This data structure is used to hold annular strand diagrams, which do not have a source

or a sink vertex. In addition:

1. An Annular object is created by invoking the method close() on a Strand object.

During the construction, the ﬁelds vertices (excluding the source and the sink)

and stackReduceSplits are copied from the corresponding Strand object.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 56

2. The ﬁeld cuttingPath is a linked list that stores a subsequence of edges in a par-

ticular cutting path in the annular strand diagram.

3. The reduce() method performs all the possible reduction moves on an annular

strand diagram, thereby reducing it.

4. The getComponents() method returns a concentrically ordered list of the connected

components in the annular strand diagram. These connected components are also

Annular objects.

5. The method encodeToPlanarGraph() (see Algorithm 10) encodes connected com-

ponents to planar graphs, which are Graph objects.

Now that the data structure has been described, we present the algorithm for the con-

jugacy problem in Thompson’s Group F in Algorithm 1. The proof of this algorithm’s

correctness comes from Theorem 2.2.3 and Theorem 3.7.1. We now begin a thorough

discussion and analysis of this algorithm.

3.3 Strand Diagram Generation

This section covers Lines 1-3 of Algorithm 1. Recall that in the string denoting an input

word, each character is an element from {x

, x

−1

, x

−1

}. Given an input word as a string

of size n, the Strand object for the word is constructed by:

1. going through each character in the input string from left to right,

2. creating a Strand object for each character encountered, and

3. concatenating these Strand objects.

The Strand object corresponding to each character in the input word is constructed

by creating at most 18 vertices and edges (see Theorem 1.4.5, note that each character

has a unit length). As shown in Algorithm 8, the method concatenate() performs the

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 57

Input: String w

, String w

Output: Whether w

and w

are conjugate: true or false

1 for w in {w

, w

} do

// generate strand diagram from word w

2 Strand sd = new Strand(w)

3 Annular asd = sd.close() // obtain annular strand diagram

4 asd.reduce() // discussed in Algorithm 2

5 List<Annular> components = asd.getComponents(asd.cuttingPath)

6 P

= new List<Graph>()

7 for c in components do

8 P

.add(c.encodeToPlanarGraph()) // see Algorithm 10

9 end

10 end

11 if P

.size() 6= P

.size() then

12 return false

13 for i = 0 −→ P

.size() − 1 do

14 Graph p

= P

.get(i)

15 Graph p

= P

.get(i)

16 if !(isIsomorphic(p

, p

)) then

// the linear algorithm proposed in [10]

17 return false

19 end

20 return true

Algorithm 1: Algorithm for the solution to the conjugacy problem in F .

concatenation of two strand diagrams in constant time. Because step (1) runs n times, it

follows that construction of the strand diagram takes O(n).

The corresponding Annular object is then produced by running the method close(),

which merges the source and the sink, and therefore closing happens in constant time.

This concludes that up to annular strand diagram generation, Algorithm 1 takes O(n).

Note 3.3.1. The edge e

, created by closing, is immediately added to the linked list called

cuttingPath that now represents a cutting path for the annular strand diagram (see (a)

in Figure 2.4.3 for visualization), and e

.node is assigned the Node that contains e

cuttingPath. Notice that e

is the ﬁrst edge added to cuttingPath. ♦

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 58

Figure 3.4.1. (a) Reduction I and (b) reduction II, with labeled edges and the split involved

in the reduction labeled v. The green vertices can be splits or merges, they may not be

distinct from each other or from the yellow vertices.

Note 3.3.2. During the creation and closing of a Strand object, the stack stackReduceSplits

stores the list of split vertices at the point of concatenations (see Algorithm 8 in the Ap-

pendix, such as the vertex v

in Figure 1.4.5. The reason for keeping this list is that, right

after the concatenation, these split vertices are the only split vertices where a reduction

(reduction II to be exact) is possible. Thus, stackReduceSplits allows us to know all

possible locations of reductions upon creation of an annular strand diagram. ♦

3.4 Reducing

In this section we discuss Line 4, of Algorithm 1, that performs all possible reductions.

This section assumes that the input word for the annular strand diagram has length n.

Our algorithm to reduce annular strand diagrams is shown in Algorithm 2. Reduction I

and reduction II are further described in Algorithm 3 and Algorithm 4 respectively. We

also emphasize the necessity of eﬃciently check for reductions and updating the cutting

path.

The major steps in reducing an annular strand diagram are discussed below:

1. We perform a stack based reduction to speed up the reduction step. Recall that the

stack stackReduceSplits initially stores all the split vertices in the annular strand

diagram that take part in a reduction, which is a reduction II (see Note 3.3.2).

2. Until this stack is empty, we continue to pop a split from the top of the stack,

set its inStack ﬁeld to false, and if the split is involved in a reduction I (Line 6,

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 59

// Algorithm to reduce annular strand diagrams:

1 while !stackReduceSplits.isEmpty() do

2 Vertex split = s.pop()

3 split.inStack = false

4 Vertex lchild = split.getLeftChild()

5 Vertex parent = split.getLeftParent()

6 if lchild.type == “merge” and split.leftChildEdge == lchild.leftParentEdge and

split.rightChildEdge == lchild.rightParentEdge then

7 reductionI(split) // See Algorithm 3

8 else if parent.type. == “merge” then

9 reductionII(split) // See Algorithm 4

11 end

// Perform Reduction III: Merge consecutive free loops

12 Node current = cuttingPath.getFirst()

13 while current.next 6= null do

14 if current.data.isFreeLoop and current.next.data.isFreeLoop then

15 current = current.next

16 cuttingPath.remove(current.previous)

17 else

18 current = current.next

20 end

Algorithm 2: The reduce() method for Strand objects. Note that reductionI() or

reductionII() may push splits into stackReduceSplits.

Algorithm 2) or a reduction II (Line 8, Algorithm 2), we perform the appropriate

reduction.

3. Notice that both reductions I and II happen around a split that is removed after

the reduction, that is, the vertex v in Figure 3.4.1. After a reduction I or a reduc-

tion II is performed, nearby split vertices may be put into the stack (discussed in

Section 3.4.1).

4. When the stack stackReduceSplits becomes empty, all the possible reductions I

and II have been performed.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 60

5. Since each of reduction I and reduction II removes two vertices, and since the total

number of vertices in the original annular strand diagram is O(n), it follows that

the total number of these reductions is also O(n).

6. Finally, we loop through all the edges in cuttingPath and merge concentrically

adjacent free loops using reduction III. Since the number of edges is O(n), it follows

that the number of reduction III moves in the worst case is bounded by O(n).

3.4.1 Keeping Track of Potential Future Reductions

We need to make sure that the number of checks for possible reduction I and reduction II

moves is bounded by O(n). An obvious algorithm to carry out all possible reductions is

to:

1. go through all the vertices in the annular strand diagram, checking for reductions,

and

2. whenever a reduction is possible, carrying it out, and

3. going to step (1) until no more reductions can be performed on the annular strand

diagram.

In the worst case, this algorithm runs O(n) times, and since there are O(n) vertices initially

that need to be checked for a possible reduction, the overall running time of this algorithm

is O(n

This is why we perform a stack based reduction which ensures that the overall number

of inquiries for possible reduction I and reduction II moves is bounded by O(n) . Notice

that whenever a reduction I or a reduction II is performed, this can give rise to a new

reduction at the split vertices around the current region of reduction. We eﬃciently keep

track of these possible reductions by:

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 61

1. pushing into stackReduceSplits all the neighboring split vertices, which can be all

of the green vertices in Figure 3.4.1.

2. setting the inStack ﬁeld of any split to true when the split is put into the stack,

and to false when it is removed from the stack. This is an optimization to decide

in constant time whether a split that should be put on the stack is already in the

stack, and to avoid adding duplicates to the stack. Note that this step only aﬀects

the overheads in the running time.

According to Figure 3.4.1, at most four vertices can be put on the stack due to a reduction I

or a reduction II. Because the total number of reduction I and reduction II moves is O(n),

it follows that the total number of items added to the stack until the annular strand

diagram is reduced is also O(n). Hence, the number of checks for possible reduction I and

reduction II moves until the strand diagram is reduced is O(n).

3.4.2 Cutting Path Update and Free Loop Generation

Here we show that updating the cutting path until the annular strand diagram is reduced

takes at most O(n), and discuss how our algorithm correctly detects all free loops arising

from reduction moves.

Note 3.4.1. cuttingPath does not store a cutting path, but stores an instance of a cutting

path. This instance has only one occurrence of each edge that the cutting path crosses,

and after the annular strand diagram is reduced, the sequence of edges in cuttingPath

is suﬃcient to correctly determine the concentric order of components. Furthermore, the

size of cuttingPath is bounded by O(n). ♦

A cutting path can cross an edge multiple times, but for our purposes, it suﬃces to

record only one crossing of each edge. Given a component C, if an edge e

∈ C crosses the

cutting path multiple times, all these crossings will happen:

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 62

// Perform Reduction I (see (a) in Figure 3.4.1 for visualization):

Input: Vertex v, the split vertex that will be removed after the reduction

1 Vertex p = v.getLeftParent()

2 Vertex gc = w.getLeftChild() // grand child of v

3 if p == w then

4 e

.makeFreeLoop() // the condition for a free loop

5 else

6 e

= e

.combineEdge(e

)

7 for nbr in {p, gc} do

8 if nbr.type == “split” and !(nbr.inStack) then

9 stackReduceSplits.push(nbr); nbr.inStack = true

11 end

12 // Cutting path update:

13 if e

.node 6= null then

14 if e

.node 6= null then

15 cuttingPath.remove(e

)

16 else

17 cuttingPath.replace(e

, e

)

18 cuttingPath.remove(e

)

19 vertices.remove(w); vertices.remove(v)

Algorithm 3: The reductionI() subroutine. Note that the replace() and remove()

methods take constant time (see Section 3.2.1).

• after the crossing of an edge from the innermost directed cycle in C, and

• before the crossing of an edge from the outermost directed cycle in C.

Therefore, we can arbitrarily record only one such occurrence of e

in cuttingPath and

still have a sequence of edges in cuttingPath that identify components in order. Because

the number of edges in the reduced annular strand diagram is bounded by O(n), it follows

that the maximum possible size of cuttingPath is also O(n).

Moreover, this is necessary to perform reductions in constant time. As will be shown in

this section, reductions modify edges, and if an edge is in cuttingPath multiple times, all

its occurrences in cuttingPath need to be updated, which is undesirable.

Note 3.4.2. cuttingPath only needs to be updated if it contains an edge that is removed

in a reduction, that is, any black edge crossed by the red edge in Figure 2.4.2. ♦

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 63

// Perform Reduction II (see (b) in Figure 3.4.1 for visualization):

1 if v.rightChildEdge == w.rightParentEdge then

2 e

.makeFreeLoop() // a free loop is created on the right edges

3 else

4 e

= e

.combineEdge(e

)

5 if v.leftChildEdge == w.leftParentEdge then

6 e

.makeFreeLoop() // a free loop is created on the left edges

7 else

8 e

= e

.combineEdge(e

)

9 for nbr in {e

.source,e

.target,e

.source,e

.target} do

10 if nbr 6= null and nbr.type == “split” and nbr.inStack == false then

11 stackReduceSplits.push(nbr); nbr.inStack = true

13 end

14 if e

.node 6= null then

15 red2CuttingUpdate() // Cutting path update (see Algorithm 5)

16 vertices.remove(v); vertices.remove(w)

Algorithm 4: The reductionII() subroutine.

Recall that the other edges in Figure 2.4.2 that may be contained in cuttingPath prior

to the reduction are modiﬁed during the reduction using the combineEdge() method,

which updates cuttingPath accordingly.

In the case of a reduction I (see (a) in Figure 3.4.1 for visualization):

• a free loop is generated only if e

and e

are the same edge prior to the reduction

(see Figure 2.2.2).

• cuttingPath does not need to be updated if it contains e

or e

because

combineEdge() ensures that there is at most one container node in cuttingPath

holding the edge created by merging e

and e

after the reduction.

• if cuttingPath contains e

, then it must also have a node holding e

(see Fig-

ure 2.4.2). In this case, if e

.node is null, then we replace the adjacent nodes

containing e

and e

in cuttingPath with e

. Otherwise, we remove e

and e

from

cuttingPath.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 64

Recall that the node ﬁeld for an Edge object stores the node that contains the edge in

cuttingPath (see Section 3.2.2). Therefore, given an edge e, the node in cuttingPath

containing e can be accessed in constant time, and consequently, updating cuttingPath

in reduction I (Lines 13 - 18 in Algorithm 3) takes a constant number of operations. It

follows that reduction I takes constant time.

// see (b) in Figure 3.4.1 for visualization

1 boolean replaced = false

2 if e

.node == null then

3 cuttingPath.replace(e

, e

)

4 replaced = true

5 if e

.node == null then

6 if replaced then

7 cuttingPath.addAfter(e

, e

)

8 else

9 cuttingPath.replace(e

, e

)

11 else if !replaced then

12 cuttingPath.remove(e

)

Algorithm 5: The red2CuttingUpdate() method, which updates cuttingPath dur-

ing a reduction II. See Section 3.2.1 for description of the methods invoked on

cuttingPath.

In the case of a reduction II (see (b) in Figure 3.4.1 for visualization):

• at most two free loops are created (see Figure 2.2.2) as shown in the cases below:

1. e

= e

, or

2. e

= e

prior to the reduction.

• we do not need to update cuttingPath if it contains the edges e

, e

, or e

since

combineEdge() will update it accordingly.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 65

• However, cuttingPath requires an update if it contains the edge e

. In this case,

after the reduction the corresponding cutting path is expected to cross e

before it

crosses e

. We have the following possible cases when updating cuttingPath:

1. If both e

and e

are not in cuttingPath, then we replace the node for e

cuttingPath ﬁrst with a node holding e

followed by a node holding e

2. If both e

or e

are already in cuttingPath, then we simply remove the node

for e

3. If exactly one of e

or e

is not in cuttingPath, then we create a new node

holding this edge and replace the node for e

with this node.

• Below we list three special cases where precaution need to be taken in updating

cuttingPath. The cases correspond to Figure 3.4.2.

(a) Prior to the reduction, the cutting path crosses e

before it crosses e

: after the

reduction, the node for e

must be contained in cuttingPath before the node

for e

(b) v.leftChildEdge = w.rightParentEdge: Make sure that the same edge is not

added twice in cuttingPath.

twice in cuttingPath.

Recall that the methods invoked on the doubly linked list cuttingPath each perform a

constant number of operations. It follows that the method red2CuttingUpdate(), which

updates the cutting path during a reduction II move, takes a constant number of opera-

tions. Thus, we can conclude that a single reduction II move executes in constant time.

At this point, we have shown that carrying out all the possible reductions I and II, that

is, the while loop starting in Line 1 of Algorithm 2, take O(n) in the worst case. Earlier in

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 66

(a) (b) (c)

Figure 3.4.2. Special cases for updating cuttingPath during a type II move. Refer to (b)

in Figure 3.4.1 for edge and vertex labels.

this section, we showed that all the reduction III moves (the while loop starting in Line

13 of Algorithm 2) are bounded by O(n). Therefore, the method reduce(), which is the

algorithm to reduce an annular strand diagram, is bounded by O(n).

3.5 Connected Component Labeling

This section describes how connected components are labeled in reduced annular strand

diagrams, which happens in Line 5 of Algorithm 1. Because each connected component is

a reduced annular strand diagram, it is represented using an Annular object. To construct

a connected component, it suﬃces to start with an edge belonging to the component and

performing a depth ﬁrst search along its source and target to ﬁnd all of the vertices in the

component. Below we discuss the major points regarding the method getComponents(),

which is comprehensively described in Algorithm 9 in the Appendix:

1. When the Annular object representing a connected component has no vertices but

has a single edge, it means that the component is a free loop.

2. getComponents() takes as input cuttingPath after the annular strand diagram has

been reduced. Recall that at this point cuttingPath is an ordered subsequence of a

cutting path for the reduced annular strand diagram, containing at least one edge

from each connected component.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 67

3. Given an edge e in cuttingPath, the algorithm proceeds by obtaining the source

vertex v of e, and then performing a depth ﬁrst search on all the edges connected to

v to discover the whole component that contains e. Any edge e

discovered during

this search has its flagged ﬁeld set to true so that if e

is in cuttingPath, a depth

ﬁrst search is not performed on e

4. Similar to the reduce() method, we again use a stack of vertices and the inStack

ﬁeld for Vertex objects to ensure that each vertex is queried only once during the

depth ﬁrst search.

Analysis of Connected Component Labeling: We will analyze all the connected

component labeling in a reduced annular strand diagram R collectively. Let the original

strand diagram corresponding to R be S, which is produced from the input word of length

n. Let V

and E

be the number of vertices and edges respectively in S. Recall from

Theorem 1.4.5 that V

+ E

≤ 15n + 3. It is easy to see that the number of vertices and

edges in R is also bounded by 15n+3. Therefore, from statement (4) above, it follows that

the while loop in Line 13 of Algorithm 9 executes O(n) times. Because each vertex in R

has a constant number of connected edges, it follows that one iteration of this while loop

performs a constant number of operations. Hence all the connected component labeling

are collectively bounded by O(n).

3.6 Encoding Annular Strand Diagrams into Planar Graphs

As mentioned in the beginning of this chapter, we reduce the problem of determining

whether two reduced annular strand diagrams are isotopic to the problem of determining

whether two planar graphs are isomorphic, and then use the linear time planar graph

isomorphism checker algorithm proposed in [10].

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 68

In this section, we cover Lines 6-9 of Algorithm 1, that is, the conversion of each con-

nected component in a reduced annular strand diagram to a corresponding planar graph.

We provide a function that encodes connected components to planar graphs, and we create

an algorithm that implements this encoding. Then we show that this algorithm is linear

in the number of vertices and edges in the reduced annular strand diagram, and therefore

linear in the length of the input word used to construct the annular strand diagram.

Let X be the set of all connected, reduced annular strand diagrams. Let G be the set

of planar graphs to which elements of X will be encoded. Let φ : X → G be the encoding

function. If s ∈ X is a free loop, then let φ encode s to the planar graph φ(s) shown in

Figure 3.6.1.

Consider the case when s is not a free loop. Observe that an edge e ∈ s is both an

output from a vertex, and an input to a vertex. As shown in Figure 3.6.2, e can be any of

the following input and output types:

Input Types for e Output Types for e

1. the lone input to a split 1. the lone output of a merge

2. the left input to a merge 2. the left output of a split

3. the right input to a merge 3. the right output of a split

Thus, there are nine unique output-input combinations, each of which deﬁnes an edge

class, which is a pair of integers (out,in) such that out represents the output type and in

represents the input type of the edge.

free loop

Figure 3.6.1. The encoding of s ∈ X when s is a free loop. φ(s) ∈ G is the planar graph

with a single vertex having a loop.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 69

output

left

input

right

input

left

output

right

output

Figure 3.6.2. Diﬀerent input and output types for edges. The vertex on the left is a merge,

and the one on the right is a split

In order to achieve unique encoding of each s ∈ X, we will generate unique planar

graphs for each possible class of edge in s. Below we discuss how we generate these planar

graphs, and how the class to which an edge e belongs, uniquely identiﬁes the corresponding

planar graph for e.

Class (1,1): Edge e

= (out

, in

) ∈ s is the output of a merge out

and the input of

a split in

. Produce the corresponding planar graph g

using the following steps:

1. Create a null graph g

having only the vertices out

and in

2. Add new vertices w

and u

to g

3. In g

, create an edge (out

, w

), two edges between w

and u

, and three edges

between u

and in

Then g

is the planar graph encoding of the edge e

. Figure 3.6.3 shows the encoding

of e

in graphical form. The other eight edge classes have encodings very similar to edge

out

out,

out

(a) e

(b) the corresponding planar graph g

Figure 3.6.3. (a) shows the highlighted edge e

which is the lone output of a merge and

the lone input to a split. The encoding of e

produces the planar graph g

in (b).

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 70

class (1,1), except that they each diﬀer in the number n

of edges created between u

and

in the corresponding planar graph. As the value of n

is unique for each class of edge

in the annular strand diagram, it follows that the encoding of each class of edge is unique.

The encodings of all the edge classes are described in Table 3.6.

We are ready to encode the reduced, connected, non-free loop annular strand diagram s.

Assume that E = {e

, e

, ...e

} is the edge set of s. To obtain φ(s), follow the steps below:

1. Create a null graph g.

2. Copy all the vertices from s to g.

3. For each edge e

= (v

out

, v

) ∈ E, create vertices w

and u

in g. Identify the

edge class in Table 3.6 to which e

belongs, and let this be the class C, where C ∈

{1, 2, 3} × {1, 2, 3}. Then create an edge (v

out

, w

), two edges (w

, e

), and p edges

, v

) where p is the number of edges (u, v

) in the planar graph corresponding

to class C in Table 3.6.

Then, g = φ(s).

Example 3.6.1. Let s ∈ X be the reduced annular strand diagram for the word x

The encoding creates the corresponding planar graph φ(s) shown in Figure 3.6.4. ♦

Figure 3.6.4. Encoding of x

to its corresponding planar graph.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 71

Class (1,1): an edge is the output of a merge

and the input of a split v

Solution: create 3 edges between u and v

out,

Class (1,2): an edge is the output of a merge

and the right input of a merge v

Solution: create 4 edges between u and v

out,

left in

Class (1,3): an edge is the output of a merge

and the right input of a merge v

Solution: create 5 edges between u and v

out,

right in

Class (2,1): an edge is the left output of a

split v

and the input of a split v

Solution: create 6 edges between u and v

left out,

Class (2,2): an edge is the left output of a

split v

and the left input of a merge v

Solution: create 7 edges between u and v

left out,

left in

Class (2,3): an edge is the left output of a

split v

and the right input of a merge v

Solution: create 8 edges between u and v

left out,

right in

Class (3,1): an edge is the right output of a

split v

and the input of a split v

Solution: create 9 edges between u and v

right out,

Class (3,2): an edge is the right output of a

split v

and the left input of a merge v

Solution: create 10 edges between u and v

right out,

left in

Class (3,3): an edge is the right output of a

split v

and the right input of a merge v

Solution: create 11 edges between u and v

right out,

right in

Table 3.6.1. Diﬀerent types of edges in the annular strand diagram, and their encodings

to planar graphs

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 72

3.6.1 The Encoding Algorithm

We now describe our implementation of an algorithm to encode components of reduced

annular strand diagrams into planar graphs. Let X be the set of reduced connected

annular strand diagrams. As shown in Algorithm 10 (in the Appendix), the method

encodeToPlanarGraph() takes as input s ∈ X, applies the encoding function φ to s,

and returns the corresponding planar graph φ(s).

Analysis of the Encoding Algorithm: Note that this analysis covers Lines 7-9 in

Algorithm 1. We will analyze the encodings of all connected components collectively using

the same approach we used to analyze the running time of connected component labeling

in Section 3.5.

Recall that given an input word of length n, all the connected components together have

sum of vertices and edges bounded by O(n). Therefore, the for loops in Line 7 and in

Line 12 execute O(n) times and each iteration of both of these loops performs a constant

number of operations. It follows that the execution eﬃciency of Algorithm 10 is O(n).

3.7 Retrieving Annular Strand Diagrams from Planar Graph

Encodings

Now we will show that given p

∈ G, the planar graph encoding of s ∈ X, we can decode p

to derive s. Observe that the vertices in p

that also belong to s share at least three edges

with at least one vertex, and they cannot share exactly two edges with any other vertices.

Using these properties, we can construct all the vertices in s from the set of vertices in p

Since each class of edge in s has a unique corresponding planar graph encoding, conversely,

each of these planar graphs correspond to a unique class of edge in s. Let P = φ(X) be

the image of φ. Let ψ : P → X be the decoding function. Let p

∈ P and p

= (V, E),

where V and E are the vertex and edge sets of g respectively. If p

is a graph with only a

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 73

single vertex having a loop, then ψ(p

) is the free loop. Otherwise we compute ψ(g) using

the steps below:

1. Create a null annular strand diagram s.

2. For each v

∈ V , if there exists u, w ∈ V such that there exist exactly one edge

, w) and exactly two edges (w, u) in E, then add v

to s.

3. For each v

in the vertex set of s, ﬁnd all v

∈ s such that u, w ∈ p

, and there exist

exactly one edge (v

, w), exactly two edges (w, u), and at least three edges (u, v

)

in E. For each v

, if the total number of edges (u, v

) is c

, then use c

to ﬁnd

the corresponding edge class C in Table 3.6, and create in s a directed edge (v

, v

)

whose output and input type are the same as that of the highlighted directed edge

in class C.

Then, s = ψ(p

). Algorithm 11 shows the decoding algorithm that produces s given p

Notice that it is the inverse of the encoding algorithm. We do not need to worry about

the execution eﬃciency of the decoding algorithm as this algorithm is not used in our

proposed solution to the conjugacy problem in F . We skip the analysis of the decoding

algorithm.

Theorem 3.7.1. Any two connected, reduced, and non-free loop Annular Strand Diagrams

and s

can be encoded into two planar graphs g

and g

respectively such that s

and

are isotopic if and only if g

and g

are isomorphic.

Proof. Let s

and s

be two connected, reduced, and non-free loop annular strand dia-

grams. Let the encoding be the function φ described in Section 3.6. In order to prove the

theorem, it suﬃces to show that the encoding is one-to-one. Let g

= φ(s

) and g

= φ(s

Assume that g

= g

. Because of the nature of φ, it immediately follows that φ(s

) = φ(s

Also, by applying the decoding function ψ, described in Section 3.7, on g

and g

, we get

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 74

the following:

= ψ(g

) = ψ(g

) = s

It follows that φ is one-to-one.

3.8 Isomorphism Checking

This section covers Lines 11-20 in Algorithm 1 and completes the analysis of the solution

algorithm. The relevant lines of code are very straightforward:

1. If the total number of planar graph encodings is not the same for both reduced

annular strand diagrams, then it immediately follows that the reduced annular strand

diagrams are not isotopic.

2. Otherwise, we take each planar graph encoding p

and p

corresponding to words

and w

respectively in order of increasing distance from the cutting path, and

then check whether p

and p

are isomorphic.

(a) If any such pair is not isomorphic, then the corresponding reduced annular

strand diagrams are not isotopic, and hence the words w

and w

are not

conjugate.

(b) If all pairs are isomorphic, then w

and w

are conjugate.

Analysis of Check for Isomorphism between Planar Graphs: Hopcroft and

Wong [10] have shown an algorithm that determines whether two planar graphs are iso-

morphic in O(|V |), where |V | is the sum of the number of vertices in the input planar

graphs. Their algorithm can also be applied on planar graphs which have loops and mul-

tiple edges between vertices such as our encoded planar graphs.

Because the total number of vertices from all our planar graph encodings are collectively

bounded by O(n), it follows that the worst case running time of the for loop starting in

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 75

Line 13 of Algorithm 1 (i.e., all the checks for isomorphism between planar graphs) is

O(n).

This proves Theorem 3.0.5 and conﬁrms that the solution we presented to the conjugacy

problem in F is linear in the sum of the length of the input words.

3.9 Our Actual Implementation

To the best of our knowledge, the linear time algorithm that checks for an isomorphism

between two planar graphs proposed in [10] used in Line 16 in Algorithm 1 has not been

implemented yet. We believe that this is due to the complicated design of the algorithm.

Moreover, the authors of [10] stated that this algorithm is not practical. As a result, we

have not attempted an implementation of this algorithm, and instead programmed a direct

isotopy search as a substitute for the following steps:

1. planar graph encoding of each component in the two annular strand diagrams, and

2. checking for isomorphism between all corresponding pairs of planar graph encodings.

Because of this change, ConjugacyF takes O(n

). We implemented Algorithm 6, which

modiﬁes Algorithm 1 by substituting the two steps above with a detector that checks the

rotation systems of two reduced annular strand diagrams to determine whether they are

isotopic. The rest of this section describes the isotopy detector, and analyzes its running

time.

Recall that our data structure provides the counterclockwise ordering of edges connected

to each vertex in an annular strand diagram. Using this information, we can create the

rotation system for two reduced annular strand diagrams, and then determine whether

one rotation system is a permutation of the other.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 76

Input: String w

, String w

Output: Whether w

and w

are conjugate: true or false

1 for w in {w

, w

} do

// generate strand diagram from word w

2 Strand sd = new Strand(w)

3 Annular asd = sd.close() // obtain annular strand diagram

4 asd.reduce() // see Algorithm 2

5 List<Annular> C

= asd.getComponents()

6 end

7 if C

.size() 6= C

.size() then

8 return false

9 for i = 0 −→ C

.size() − 1 do

10 Annular c

= C

.get(i)

11 Annular c

= C

.get(i)

12 if !isIsotopic(c

, c

) then

// see Algorithm 13 in the Appendix

13 return false

15 end

16 return true

Algorithm 6: Our working implementation ConjugacyF

By convention, we obtain the edges for a merge starting with the left parent edge and

going counterclockwise. In the case of splits, we start with the left child edge and move

counterclockwise.

3.9.1 Isotopy Detector Given two Corresponding Vertices

First we discuss the method isotopyHelper(), our implementation to check whether

two two connected, reduced annular strand diagrams c

and c

are isotopic given two

corresponding vertices ref ∈ c

and corr ∈ c

. A brief outline of the ﬂow of this algorithm

is shown below, and a comprehensive description is provided in Algorithm 12 (in the

Appendix). Note that the term edge cycle refers to a counterclockwise order of edges

connected to a vertex.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 77

1. This algorithm proceeds by checking whether the edge cycles of the vertices ref and

corr are the same, which happens when these vertices are of the same type (i.e.,

both merges or both splits) and the vertex at the other end of an edge e ∈ ref is

of the same type as the vertex at the other end of its corresponding edge e

∈ corr,

for all edges in the edge cycle of ref.

2. If step (1) successfully checks out, then for each edge e in the edge cycle of ref,

the vertices v connected to e and v

connected to its correspondent e

in the edge

cycle of corr are marked using the ﬁeld isPaired, v

is set as the corresponding

vertex of v using the ﬁeld correspondent, and v is added to a stack. The function of

isPaired is to avoid putting a vertex on the stack more than once, which guarantees

that each edge cycle in c

is assigned exactly one corresponding edge cycle in c

, and

correspondent records the correspondence between an edge cycle in c

and an edge

cycle in c

3. While the stack is not empty, a vertex v

is popped from the stack, and the algo-

rithm loops back to step (1) with v

as the reference and v

.correspondent as its

correspondent.

4. If each vertex v

∈ c

is successfully assigned a unique corresponding vertex v

∈ c

then the algorithm declares that c

and c

are isotopic.

Analysis of isotopyHelper(): Given that the sum of the vertices in c

and c

is N,

since:

1. the total number of vertices added to the stack is less than N , and

2. there is a constant number of edges connected to each vertex

it follows that the execution of isotopyHelper() (see Algorithm 12) takes O(N).

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 78

3.9.2 Isotopy Detector Given two Connected Reduced Annular Strand Diagrams

We now describe the method isIsotopic(), which determines whether two connected,

reduced annular strand diagrams c

and c

are isotopic. As shown in Algorithm 13 (in

the Appendix), this method proceeds by ﬁxing a vertex reference ∈ c

and then loop-

ing through all vertices v ∈ c

to check whether c

and c

are isotopic with reference

corresponding to any such v, using isotopyHelper().

Analysis of isIsotopic(): Assuming that the sum of the vertices in c

and c

is N, in

the worst case, the for loop in Line 6 runs O(N) times. Each execution of Line 10 inside

this for loop takes O(N) in the worst case. It follows that the method isIsotopic(),

summarized in Algorithm 13 takes O(N

Analysis of the algorithm that determines whether two Reduced Annular

Strand Diagrams are Isotopic: We will analyze this step in the same way we analyzed

connected component labeling earlier, that is, we collectively analyze whether all corre-

sponding connected components of two reduced annular strand diagrams are isotopic.

Let A

and A

be two reduced annular strand diagrams each corresponding to an input

word of length O(n). Recall that the number of vertices in A

and A

is bounded by O(n).

The worst case happens when all corresponding components are isotopic except the last

ones, which are “almost” isotopic. For this case, let C

, ..., C

be the components of A

in concentric order with such that for each C

, the number of vertices is denoted by V

Then, for each C

, the call to isIsotopic() in Line 12 of Algorithm 6 takes O((V

)

Then all the calls to isIsotopic() collectively take

O((V

)

) + O((V

)

) + ... + O((V

)

) ≈ O((V

)

+ (V

)

+ ... + (V

)

However, observe that (V

)

+ (V

)

+ ... + (V

)

< n

It follows that all the calls to isIsotopic() in the if statement in Line 12 are collec-

tively bounded by O(n

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 79

Therefore, our working implementation ConjugacyF for the conjugacy problem in

Thompson’s Group F has running time O(n

3.10 Results

n p, the No. of vertices in reduced annular diagrams

0 2 4 6 8 10 12 14 16 18 20 22 24 26

1 0 4 0 0 0 0 0 0 0 0 0 0 0 0

2 0 6 6 0 0 0 0 0 0 0 0 0 0 0

3 0 6 10 8 0 0 0 0 0 0 0 0 0 0

4 0 8 16 14 12 0 0 0 0 0 0 0 0 0

5 0 8 26 40 22 16 0 0 0 0 0 0 0 0

6 0 8 34 58 56 34 28 0 0 0 0 0 0 0

7 0 8 44 98 124 98 62 40 0 0 0 0 0 0

8 0 8 56 156 240 234 194 106 72 0 0 0 0 0

9 0 8 60 228 452 536 476 368 202 120 0 0 0 0

10 1 8 68 314 756 1108 1148 954 742 378 216 0 0 0

11 1 8 68 386 1204 2136 2638 2434 1990 1474 730 376 0 0

12 1 8 72 480 1806 3790 5436 5794 5324 4160 2988 1472 704 0

Table 3.10.1. Each entry in the table shows the number of unique reduced annular strand

diagrams having p vertices obtained using words of length up to n.

In this section, we verify that the Java implementation of ConjugacyF is correct and

bug-free by using ConjugacyF on a large number of inputs and showing that the outputs

are free of error.

Notice that each conjugacy class in F corresponds to a unique reduced annular strand

diagram. In our experiment, ﬁrst we computed all the cyclically reduced words starting

from length n = 1 up to n = 12, and sorted them into conjugacy classes using ConjugacyF.

Then, for each value of n. we tabulated the total number of unique reduced annular strand

diagrams with number of vertices in the set {0, 2, 4, ..., 26}. The results are summarized

in Table 3.10.1. Note that there exists no reduced annular strand diagram with an odd

number of vertices because the number of merge and splits have to be the same (i.e., both

odd or both even).

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 80

3.10.1 Veriﬁcation of Results

We will now analyze the total number of conjugacy classes with two vertices and with four

vertices obtained using our algorithm and verify that they are correct.

Conjugacy classes with two vertices: Observe that all reduced annular strand di-

agrams with two vertices can be generalized into the same basic structure shown in Fig-

ure 3.10.1. In this structure,

1. the edge connecting the two vertices can have two possible directions,

2. there can be a free loop in the innermost region, and

3. a free loop in the outermost region,

giving 2 × 2 × 2 = 8 unique reduced annular strand diagrams. This is in accordance with

the column p = 2 in Table 3.10.1, where the entries reach their maximum value 8 as n is

increased to 4. Furthermore, each of the following 8 words was the ﬁrst input for which

ConjugacyF found a unique reduced annular strand diagram with 2 vertices:

−1

We veriﬁed these results by manually drawing and reducing the annular strand diagrams

corresponding to these words.

Figure 3.10.1. A general structure for reduced annular strand diagrams with two vertices.

The red dashed circles show free loops.

3. ALGORITHM FOR THE CONJUGACY PROBLEM IN F 81

General Structure Unique Reduced Annular Strand Diagrams Generated

1 × 2 choices for edge directions

2 × 2 choices for free loops